LeetCode刷题之树的解题方法及相关练习

以你之姓@ 2023-03-01 09:11 24阅读 0赞

**1.** [多味的LeetCode — 98. 验证二叉搜索树][LeetCode _ 98.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            return dfs(root, INT_MIN, INT_MAX);
        }
        bool dfs(TreeNode* root, long long minv, long long maxv){
            if (!root) return true;
            if (root -> val < minv || root -> val > maxv) return false;
            return dfs(root -> left , minv,  root -> val - 1ll) && dfs(root -> right, root -> val + 1ll, maxv); 
    
        }
    };

**2.** [多味的leetcode — 94.二叉树的中序遍历][leetcode _ 94.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
        
    public:
        vector<int> inorderTraversal(TreeNode* root) {
        
            vector<int> res;
            stack<TreeNode *> stk;  //首先定义一个栈
            auto p = root; //用p来遍历整棵树
            while(p || stk.size())
            {
        
                while(p)
                {
        
                    stk.push(p);
                    p = p -> left;
                }
                p = stk.top(); // 栈顶元素输出
                stk.pop();
                res.push_back(p -> val);
                p = p -> right;
            }
            return res;
        }
    };

**3.** [快乐的LeetCode — 101. 对称二叉树][LeetCode _ 101.]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 2]  
**递归写法：**

class Solution {
        
    public:
        bool isSymmetric(TreeNode* root) {
        
            if(!root) return true;
            return dfs(root -> left,root -> right);
        }
        bool dfs(TreeNode* p, TreeNode* q){
        
            if (!p || !q) return (!p) && (!q);
            return p -> val == q -> val && dfs(p -> left, q -> right) && dfs(p -> right, q -> left);
        }
    };

**迭代写法：**  
左边：左中右  
右边：右中左

class Solution{
        
    public:
        bool isSymmetric(TreeNode* root) {
        
            if(!root) return true;
            stack<TreeNode*> left, right;
            auto l = root->left, r = root->right;
            while(l || r || left.size() || right.size())
            {
        
                while(l && r)
                {
        
                    left.push(l), l = l-> left;
                    right.push(r), r = r -> right;
                }
                if(l || r) return false;
                l = left.top(), left.pop();
                r = right.top(), right.pop();
                if (l->val != r->val) return false;
                l = l -> right, r = r -> left;
            }
            return true; 
        }
    };

**4.** [多味的LeetCode — 剑指offer面试题 06. 重建二叉树][LeetCode _ _offer_ 06.]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 3]  
**5.** [快乐的LeetCode之遍历二叉树之前序、中序、后序、层序][LeetCode]

class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    
    #层序遍历BFS
    class Solution:
        def LevelorderTraversal(self, root):
    
            if root is None:
                return []
            res, cur_level = [], [root]
            while cur_level:
                temp = []
                next_level = []
                for i in cur_level:
                    temp.append(i.val)
                    if i.left:
                        next_level.append(i.left)
                    if i.right:
                        next_level.append(i.right)
                res.append(temp)       #  层序遍历每一层都是一个一维数组
                cur_level = next_level # 不像之前的pop，这里直接是把每一层的左右子树直接赋值给cur_level.
            return res                # res的结果形式是类似于：[[...], [...], [...]]

[LeetCode _ 98.]: https://blog.csdn.net/weixin_43283397/article/details/105927583
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/b6506f12094f42fb8e5775ada7f86595.png
[leetcode _ 94.]: https://blog.csdn.net/weixin_43283397/article/details/105003665
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230209/2769094170b24a568050c36d1f58b10c.png
[LeetCode _ 101.]: https://blog.csdn.net/weixin_43283397/article/details/106895122
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200622085115585.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center
[LeetCode _ _offer_ 06.]: https://blog.csdn.net/weixin_43283397/article/details/104493808
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200810164049835.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center
[LeetCode]: https://blog.csdn.net/weixin_43283397/article/details/105004503