频率很高的手写代码面试题--二叉树类型(下)

一时失言乱红尘 2023-06-16 12:00 16阅读 0赞

### 频率很高的面试题--二叉树类型 ###

*   *   *  1、相同的树
         *  2、验证二叉搜索树
         *  3、对称二叉树
         *  4、左叶子之和
         *  5、二叉树的右视图
         *  6、序列化二叉树
         *  7、 二叉树路径总和
         *  8、求根到叶子节点数字之和
         *  9、 最小高度树

### 1、相同的树 ###

给定两个二叉树，编写一个函数来检验它们是否相同

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

**思路：**  
（1）如果两个节点都为空，则返回True

（2）如果都不为空且相等，则要进行递归往左和往右遍历

（3）如果上述条件都不满足，假如：一个为空、一个不为空、或者节点值不相等，这些情况直接返回False

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
            if p==None and q==None:
                return True
            
            if p!=None and q!=None and p.val ==q.val:
                return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
            else:
                return False

方法二：

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
            if q and p:
                return p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
            # 如果他们都为空则返回True,否则返回False
            return q is p
            # return q == p

### 2、验证二叉搜索树 ###

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。  
节点的右子树只包含大于当前节点的数。  
所有左子树和右子树自身必须也是二叉搜索树。

> 示例  
> 输入:
> 
>     2
>      / \
>     1   3
>     输出: true
>     示例

> 输入:
> 
>     5
>      / \
>     1   4
>        / \
>       3   6
>       
>     输出: false
>     解释: 输入为: [5,1,4,null,null,3,6]
>     根节点的值为 5 ，但是其右子节点值为 4

验证二叉树其实最简单的思想就是进行中序遍历的判断，因为二叉树中序的序列式递增的序列。

但是我们在比较的时候，**不能用根节点和左右子树去比较，这其实是一个误区 ！**

比如下面案例：

>     5
>      / \
>     1   7
>        / \ 
>       6   8

思路：递归思想。首先看的根节点，根节点的值不能和1,7比较，7应该介于int 和 -int 之间

然后如果满足，则往左递归，这时候和1节点比较的是 -int 和 5，再往左递归发现是none，则返回，然后往右递归也是空，返回。

接着，还是往右递归，这时候root 节点值为7，节点7不能和6,8比较，应该和 5，int 比较，如果满足则往左递归，root的值是6，这时候6比较的是5,7它应该介于5，7之间…

# class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    
    class Solution:
        def isValidBST(self, root: TreeNode) -> bool:
            def juedge(left,root,right):
                if not root:
                    return True
                if left<root.val<right:
                    return juedge(left,root.left,root.val) and juedge(root.val,root.right,right)
                else:
                    return False
            return juedge(-float('INF'),root,float('INF'))
            # inf 代表正无穷，-inf 代表负无穷

### 3、对称二叉树 ###

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 \[1,2,2,3,4,4,3\] 是对称的。

1
       / \
      2   2
     / \ / \
    3  4 4  3
    
    但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    
        1
       / \
      2   2
       \   \
       3    3

思路：  
(1)如果左子树或右子树有一个为空，则判断两个是否都为空，如果都为空则返回 True,否则返回 False

(2)如果两个节点值不相等返回 False,否则进行递归判断

class Solution:
        def isSymmetric(self, root: TreeNode) -> bool:
            if not root:
                return True
            def judeg(lroot,rroot):
                if not lroot or rroot:
                    return lroot is rroot
                if lroot.val != rroot.val:
                    return False
                return judeg(lroot.left,rroot.right) and judeg(lroot.right,rroot.left)
            return judeg(root.left,root.right)

方法二：

class Solution(object):
        def isSymmetric(self, root):
            def is_mirror(left, right):
                if not left and not right:
                    return True
                if not left or not right:
                    return False
                
                return left.val==right.val and is_mirror(left.left, right.right) and is_mirror(left.right, right.left)
            return not root or is_mirror(root.left, root.right)

### 4、左叶子之和 ###

计算给定二叉树的所有左叶子之和

3
       / \
      9  20
        /  \
       15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

方法一：递归

def sumOfLeftLeaves(self, root: TreeNode) -> int:
            if not root:
                return 0
    		# 判断左子树是否符合条件
            if root.left and not root.left.left and not root.left.right:
                return root.left.val + self.sumOfLeftLeaves(root.right)
            # 进行递归
            return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

方法二：非递归

用一个队列对二叉树进行层序遍历，如果是左子树的叶子节点，则加入返回变量中

int sumOfLeftLeaves(TreeNode* root) { 
            queue<TreeNode*>q;
            if(root == nullptr){ 
                return 0;
            }
            q.push(root);
            int ans = 0;
            while(!q.empty()){ 
                TreeNode* temp = q.front();
                q.pop();
                if(temp->left && temp->left->left == nullptr 
                    && temp->left->right == nullptr){ 
    
                    ans+=temp->left->val;
                }
                if(temp->left){ 
                    q.push(temp->left);
                }
                if(temp->right){ 
                    q.push(temp->right);
                }
            }
            return ans;
        }

### 5、二叉树的右视图 ###

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值

> 示例  
> 输入: \[1,2,3,null,5,null,4\]  
> 输出: \[1, 3, 4\]

1
      / \
     2   3
      \   \
       5   4

思路：其实就是个层次遍历，然后把每层的最后一个节点附加到返回列表中。

def rightSideView(self, root: TreeNode) -> List[int]:
            if not root:
                return []
            temp = [root]
            res = []
            while temp:
                res.append(temp[-1].val)
                temp = [kid for node in temp for kid in [node.left,node.right]if kid]
            return res

C++版本

vector<int> rightSideView(TreeNode* root) { 
            vector<int>res;
            if(!root){ 
                return res;
            }
            queue<TreeNode*>q;
            q.push(root);
            while (!q.empty()){ 
                int size = q.size();
                res.push_back(q.front()->val);
                while (size--){ 
                    TreeNode* temp = q.front();
                    q.pop();
                    if (temp->right){ 
                        q.push(temp->right);
                    }
                    if (temp->left){ 
                        q.push(temp->left);
                    }
                }
            }
            return res;
        }

### 6、序列化二叉树 ###

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（\#），以 ！ 表示一个结点值的结束(value!)

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树

class Solution { 
    public:
        char* Serialize(TreeNode *root) {     
            buf.clear();
            SerializePre(root);
            int size = buf.size();
            int* res = new int[size];
            for(int i = 0;i < size;++i){ 
                res[i] = buf[i];
            }
            return (char*)res;
        }
        TreeNode* Deserialize(char *str) { 
            int* p = (int*)str;
            return DeserializePre(p);
        }
    private:
        // 进行前序遍历,序列化二叉树
        void SerializePre(TreeNode *root){ 
            if(root == nullptr){ 
                buf.push_back(0xFFFFFFFF);
            }else{ 
                buf.push_back(root->val);
                SerializePre(root->left);
                SerializePre(root->right);
            }
        }
        // 反序列化二叉树
        TreeNode* DeserializePre(int* &p){ 
            if(*p == 0xFFFFFFFF){ 
                p++;
                return nullptr;
            }
            TreeNode* res = new TreeNode(*p);
            p++;
            res->left = DeserializePre(p);
            res->right = DeserializePre(p);
            return res;
        }
    private:
        vector<int>buf;
    };

### 7、 二叉树路径总和 ###

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和

说明: 叶子节点是指没有子节点的节点。

> 示例：给定如下二叉树，以及目标和 sum = 22

5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

思路：由于是从根节点到叶子节点，所以判定条件是

`if not root.left and not root.right and if root.val == target:`

class Solution { 
    public:
        bool hasPathSum(TreeNode* root, int sum) { 
            if(root == nullptr){ 
                return false;
            }
            if(root->val == sum && root->left == nullptr && root->right == nullptr){ 
                return true;
            }
            return hasPathSum(root->left,sum-root->val) ||
            hasPathSum(root->right,sum - root->val);
        }
    };

进阶

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

> 示例  
> 给定如下二叉树，以及目标和 sum = 22

5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

> 返回：  
> \[  
> \[5,4,11,2\],  
> \[5,8,4,5\]  
> \]

思路还是和上一题大致相同，参数多加了一个路径 path

class Solution { 
    public:
        vector<vector<int>>ans;
        vector<int>tmp;
        void dfs(TreeNode* root,int sum){ 
            if(root == nullptr) return;
            tmp.push_back(root->val);
            if(root->val == sum && root->left == nullptr &&\
            	root->right == nullptr){ 
                ans.push_back(tmp);
            }
            dfs(root->left,sum-root->val);
            dfs(root->right,sum-root->val);
            tmp.pop_back();
        }
        vector<vector<int>> pathSum(TreeNode* root, int sum) { 
            dfs(root,sum);
            return ans;
        }
    };

### 8、求根到叶子节点数字之和 ###

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

> 示例1
> 
>     输入: [1,2,3]
>       1
>      / \
>     2   3
>     输出: 25

> 解释:  
> 从根到叶子节点路径 1->2 代表数字 12.  
> 从根到叶子节点路径 1->3 代表数字 13.  
> 因此，数字总和 = 12 + 13 = 25.

> 示例2
> 
>     输入: [4,9,0,5,1]
>         4
>        / \  
>       9   0
>      / \
>     5   1
>     输出: 1026

> 解释:  
> 从根到叶子节点路径 4->9->5 代表数字 495.  
> 从根到叶子节点路径 4->9->1 代表数字 491.  
> 从根到叶子节点路径 4->0 代表数字 40.  
> 因此，数字总和 = 495 + 491 + 40 = 1026.

class Solution { 
    public:
        int sum = 0;
        void clac(TreeNode* root,int num){ 
            if(root->left == nullptr && root->right == nullptr){ 
                sum += num*10 + root->val;
            }
            if(root->left){ 
                clac(root->left,num*10+root->val);
            }
            if(root->right){ 
                clac(root->right,num * 10+root->val);
            }
        }
        int sumNumbers(TreeNode* root) { 
            if(root == nullptr){ 
                return 0;
            }
            clac(root,0);
            return sum;
        }
    };

### 9、 最小高度树 ###

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

> 示例:  
> 给定有序数组: \[-10,-3,0,5,9\],  
> 一个可能的答案是：\[0,-3,9,-10,null,5\]

class Solution { 
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) { 
            if(nums.size() == 0){ 
                return nullptr;
            }
            int mid = nums.size()/2;
            TreeNode* root = new TreeNode(nums[mid]);
            vector<int>left(nums.begin(),nums.end()-(nums.size()-mid));
            vector<int>right(nums.begin()+mid+1,nums.end());
            root->left = sortedArrayToBST(left);
            root->right = sortedArrayToBST(right);
            return root;
        }
    };