LeetCode 热题 HOT 100：二叉树专题

墨蓝 2023-10-15 15:33 39阅读 0赞

LeetCode 热题 HOT 100：[https://leetcode.cn/problem-list/2cktkvj/][https_leetcode.cn_problem-list_2cktkvj]

--------------------

#### 文章目录 ####

*   *  94. 二叉树的中序遍历 ---- 递归与非递归
     *  补充：144. 二叉树的前序遍历 ---- 递归与非递归
     *  补充：145. 二叉树的后序遍历 ---- 递归与非递归
     *  96. 不同的二叉搜索树
     *  98. 验证二叉搜索树
     *  101. 对称二叉树
     *  102. 二叉树的层序遍历
     *  104. 二叉树的最大深度
     *  105. 从前序与中序遍历序列构造二叉树
     *  114. 二叉树展开为链表
     *  124. 二叉树中的最大路径和
     *  226. 翻转二叉树
     *  538. 把二叉搜索树转换为累加树
     *  543. 二叉树的直径
     *  617. 合并二叉树

--------------------

### 94. 二叉树的中序遍历 ---- 递归与非递归 ###

题目链接：[https://leetcode.cn/problems/binary-tree-inorder-traversal/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_binary-tree-inorder-traversal_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

**递归方式：**

class Solution {
        
        List<Integer> list = new ArrayList<>();
    
        public List<Integer> inorderTraversal(TreeNode root) {
        
            InOrder(root);
            return list;
        }
    
        public void InOrder(TreeNode root){
        
            if(root != null){
        
                InOrder(root.left);
                list.add(root.val);
                InOrder(root.right);
            }
        }
    }

**非递归方式：**

class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈
            List<Integer> list = new ArrayList<>();
            TreeNode p = root;
            while(p != null || !stack.isEmpty()){
        
                if(p != null){
        
                    stack.push(p);
                    p = p.left;
                }else{
        
                    p = stack.pop();
                    list.add(p.val);
                    p = p.right;
                }
            }
            return list;
        }
    }

--------------------

### 补充：144. 二叉树的前序遍历 ---- 递归与非递归 ###

题目链接：[https://leetcode.cn/problems/binary-tree-preorder-traversal/description/][https_leetcode.cn_problems_binary-tree-preorder-traversal_description]

**递归做法：**

class Solution {
        
        List<Integer> list = new ArrayList<>();
    
        public List<Integer> preorderTraversal(TreeNode root) {
        
            preOrder(root);
            return list;
        }
    
        public void preOrder(TreeNode root){
        
            if(root != null){
        
                list.add(root.val);
                preOrder(root.left);
                preOrder(root.right);
            }
        }
    }

**非递归做法：**

class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈
            List<Integer> list = new ArrayList<>();
            TreeNode p = root;
            while(p != null || !stack.isEmpty()){
        
                if(p != null){
        
                    list.add(p.val);
                    stack.push(p);
                    p = p.left;
                }else{
        
                    p = stack.pop();
                    p = p.right;
                }
            }
            return list;
        }
    }

--------------------

### 补充：145. 二叉树的后序遍历 ---- 递归与非递归 ###

题目链接：[https://leetcode.cn/problems/binary-tree-postorder-traversal/description/][https_leetcode.cn_problems_binary-tree-postorder-traversal_description]

**递归做法：**

class Solution {
        
        List<Integer> list = new ArrayList<>();
    
        public List<Integer> postorderTraversal(TreeNode root) {
        
            postOrder(root);
            return list;
        }
    
        public void postOrder(TreeNode root){
        
            if(root != null){
        
                postOrder(root.left);
                postOrder(root.right);
                list.add(root.val);
            }
        }
    }

**非递归做法：**

class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> list = new ArrayList<>();
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode p, r;
            p = root;
            r = null;
            while(p != null || !stack.isEmpty()){
        
                if(p != null){
         // 走到最左边
                    stack.push(p);
                    p = p.left;
                }else{
         // 向右
                    p = stack.peek(); // 得到栈顶元素
                    if(p.right != null && p.right != r){
         // 右子树存在，且未访问
                        p = p.right;
                    }else{
         // 否则弹出节点并访问
                        p = stack.pop();
                        list.add(p.val);
                        r = p; // 记录最近访问节点
                        p = null; // 节点访问后，重置 p
                    }
                }
            }
            return list;
        }
    }

--------------------

### 96. 不同的二叉搜索树 ###

题目链接：[https://leetcode.cn/problems/unique-binary-search-trees/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_unique-binary-search-trees_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

**动态规划：**

*  假设 **`n`** 个节点存在二叉搜索树的个数是 **`G(n)`**，令 **`f(i)`** 为以 **`i`** 为根的二叉排序树的个数，则：**`G(n) = f(1) + f(2) + … + f(n-1) + f(n)`**
 *  当 **`i`** 为根节点时，由于是二叉搜索树，则其左子树节点个数为 **`i-1`** 个，右子树节点为 **`n-i`** 个，得：**`f(i) = G(i-1) * G(n-i)`**
 *  综上可得卡特兰数的公式：  
    **`G(n) = f(1) + f(2) + … + f(n-1) + f(n)`**  
       **`= G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-2) * G(1) + G(n-1) * G(0)`**

class Solution {
        
        public int numTrees(int n) {
        
            int[] dp = new int[n+1]; // dp[i] 代表 i 个节点存在二叉搜索树的个数
            dp[0] = 1;
            dp[1] = 1;
    
            for(int i = 2; i <= n; i ++){
        
                for(int j = 0; j < i; j ++){
        
                    dp[i] += dp[j]*dp[i-1-j];
                }
            }
            return dp[n];
        }
    }

--------------------

### 98. 验证二叉搜索树 ###

题目链接：[https://leetcode.cn/problems/validate-binary-search-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_validate-binary-search-tree_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

**递归中序遍历：**

class Solution {
        
        long max = Long.MIN_VALUE;
        public boolean isValidBST(TreeNode root) {
        
            if(root == null){
        
                return true;
            }
            if(!isValidBST(root.left)){
        
                return false;
            }
            if(root.val <= max){
        
                return false;
            }else{
        
                max = root.val;
            }
            return isValidBST(root.right);
        }
    }

**非递归中序遍历：**

class Solution {
        
        public boolean isValidBST(TreeNode root) {
        
            Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈
            List<Integer> list = new ArrayList<>();
            TreeNode p = root;
            long max = Long.MIN_VALUE;
            while(p != null || !stack.isEmpty()){
        
                if(p != null){
        
                    stack.push(p);
                    p = p.left;
                }else{
        
                    p = stack.pop();
                    if (p.val <= max){
        
                       return false;
                    }else{
        
                        max = p.val;
                    }
                    list.add(p.val);
                    p = p.right;
                }
            }
            return true;
        }
    }

--------------------

### 101. 对称二叉树 ###

题目链接：[https://leetcode.cn/problems/symmetric-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_symmetric-tree_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if(root == null){
        
                return false;
            }
            return recur(root.left, root.right);
        }
    
        public boolean recur(TreeNode l, TreeNode r){
        
            if(l == null && r == null){
        
                return true;
            }
            if(l == null || r == null || l.val != r.val){
        
                return false;
            }
            return recur(l.left, r.right) && recur(l.right, r.left);
        }
    }

--------------------

### 102. 二叉树的层序遍历 ###

题目链接：[https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_binary-tree-level-order-traversal_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

**双端队列模拟队列实现层序遍历：**

class Solution {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> res = new ArrayList<>();
            Deque<TreeNode> queue = new LinkedList<>();
            if(root != null){
        
                queue.push(root);
            }
            while(!queue.isEmpty()){
        
                List<Integer> list = new ArrayList<>();
                for(int i = queue.size(); i > 0; i --){
         // 注意避坑点：queue.size()，在出队时会发生变化，因此实现用 i 记录队列长度，倒序循环
                    TreeNode p = queue.remove();
                    list.add(p.val);
                    if(p.left != null){
        
                        queue.add(p.left);
                    }
                    if(p.right != null){
        
                        queue.add(p.right);
                    }
                }
                res.add(list);
            }
            return res;
        }
    }

--------------------

### 104. 二叉树的最大深度 ###

题目链接：[https://leetcode.cn/problems/maximum-depth-of-binary-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_maximum-depth-of-binary-tree_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

**深搜DFS：**

class Solution {
        
        public int maxDepth(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }

**广搜BFS：**

class Solution {
        
        public int maxDepth(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }
            Deque<TreeNode> queue = new LinkedList<>();
            TreeNode p = root;
            int depth = 0;
            queue.add(root);
            while(!queue.isEmpty()){
        
               	 int size = queue.size();
                 for(int i = queue.size(); i > 0; i --){
        
                    p = queue.remove();
                    if(p.left != null){
        
                        queue.add(p.left);
                    }
                    if(p.right != null){
        
                        queue.add(p.right);
                    }
                }
                depth++;
            }
            return depth;
        }
    }

--------------------

### 105. 从前序与中序遍历序列构造二叉树 ###

题目链接：[https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_construct-binary-tree-from-preorder-and-inorder-traversal_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

class Solution {
        
        public TreeNode buildTree(int[] preorder, int[] inorder) {
         // 先序，中序
            return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
        }
    
        public TreeNode build(int[] preorder, int lpre, int rpre, int[] inorder, int lmid, int rmid){
         // 先序左边界、右边界，中序左边界、右边界
            if(lmid>rmid || lpre>rpre){
        
                return null;
            }
            TreeNode node = new TreeNode(preorder[lpre]);
            int fa = lpre; // fa代表中序遍历数组中的根节点的索引
            for(int i = lmid; i <= rmid; i ++){
        
                if(inorder[i] == preorder[lpre]){
        
                    fa = i;
                    break;
                }
            }
            int len = fa-lmid; // 左子树的长度
            // 先序（根左右）：左边界+1、左边界+长度，中序（左根右）：左边界、根节点位置-1
            node.left = build(preorder, lpre+1, lpre+len, inorder, lmid, fa-1);
            // 先序（根左右）：左边界+长度+1、右边界，中序（左根右）：根节点位置+1、右边界
            node.right = build(preorder, lpre+len+1, rpre, inorder, fa+1, rmid);
            return node;
        }
    }

参考思路：[团体程序设计天梯赛-练习集 L2-011 玩转二叉树 (25分) 先序中序建树 思路详解][-_ L2-011 _ _25_ _]

--------------------

### 114. 二叉树展开为链表 ###

题目链接：[https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_flatten-binary-tree-to-linked-list_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

**原始做法：** 将节点前序遍历存储在集合当中，然后对集合中的节点依次展开。

class Solution {
        
        public void flatten(TreeNode root) {
        
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode p = root;
            List<TreeNode> list = new LinkedList<>();
    
            while(p!=null||!stack.isEmpty()){
        
                if(p!=null){
        
                    stack.push(p);
                    list.add(p);
                    p = p.left;
                }else{
        
                    p = stack.pop();
                    p = p.right;
                }
            }
            TreeNode q = root;
            for (int i = 1; i < list.size(); i++) {
        
                q.left = null;
                q.right = list.get(i);
                q = list.get(i);
            }
        }
    }

**优化后做法：**利用先序遍历 根左右 的特点。将根的右侧指向左子树，左子树的最右节点指向原来根的右子树，并将左子树置为空。

class Solution {
        
        public void flatten(TreeNode root) {
        
            TreeNode curr = root; // 当前节点指向根
            while(curr != null){
        
                if(curr.left != null){
        
                    TreeNode next = curr.left; // 左子树
                    TreeNode pre = next;
                    while(pre.right != null){
         // 查询左子树的最右节点
                        pre = pre.right;
                    }
                    pre.right = curr.right; // 最右节点的右指针指向当前节点的右子树
                    curr.right = next; // 当前节点的右子树指向当前节点的左子树的根
                    curr.left = null; // 当前节点左子树置为空
                }
                curr = curr.right;
            }
        }
    }

--------------------

### 124. 二叉树中的最大路径和 ###

题目链接：[https://leetcode.cn/problems/binary-tree-maximum-path-sum/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_binary-tree-maximum-path-sum_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

*  二叉树 abc，a 是根结点（递归中的 root），bc 是左右子结点（代表其递归后的最优解）。最大的路径，可能的路径情况：  
      `a`  
     `/ \`  
    `b c`  
    ① b + a + c。  
    ② b + a + a 的父结点。（需要再次递归）  
    ③ a + c + a 的父结点。（需要再次递归）
 *  其中情况 1，表示如果不联络父结点的情况，或本身是根结点的情况。这种情况是没法递归的，但是结果有可能是全局最大路径和，因此可以在递归过程中通过比较得出。
 *  情况 2 和 3，递归时计算 a+b 和 a+c，选择一个更优的方案返回，也就是上面说的递归后的最优解。

class Solution {
        
        int max = Integer.MIN_VALUE;
    
        public int maxPathSum(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }
            dfs(root);
            return max;
        }
    
        /**
         * 返回经过root的单边分支最大和， 即 Math.max(root, root+left, root+right)
         */
        public int dfs(TreeNode root){
        
            if(root == null){
        
                return 0;
            }
            // 计算左子树最大值，左边分支如果为负数还不如不选择
            int leftMax = Math.max(0, dfs(root.left));
            // 计算右子树最大值，右边分支如果为负数还不如不选择
            int rightMax = Math.max(0, dfs(root.right));
    
            // left->root->right 作为路径与已经计算过历史最大值做比较
            max = Math.max(max, leftMax + root.val + rightMax);
    
            // 返回经过root的单边最大分支给当前root的父节点计算使用
            return root.val + Math.max(leftMax, rightMax);
        }
    }

参考：[【二叉树中的最大路径和】递归，条理清晰][Link 1]

--------------------

### 226. 翻转二叉树 ###

题目链接：[https://leetcode.cn/problems/invert-binary-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_invert-binary-tree_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

**递归做法：**

class Solution {
        
        public TreeNode invertTree(TreeNode root) {
        
            overturnTree(root);
            return root;
        }
    
        public void overturnTree(TreeNode root){
        
            if(root == null){
        
                return;
            }
            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;
    
            overturnTree(root.left);
            overturnTree(root.right);
        }
    }

**非递归做法：** 利用层次遍历，在每层放入队列之后，交换左右节点。

class Solution {
        
        public TreeNode invertTree(TreeNode root) {
        
            if(root == null){
        
                return null;
            }
            Deque<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while(!queue.isEmpty()){
        
                TreeNode p = queue.remove();
                if(p.left != null){
        
                    queue.add(p.left);
                }
                if(p.right != null){
        
                    queue.add(p.right);
                }
                TreeNode tmp = p.left;
                p.left = p.right;
                p.right = tmp;
            }
            return root;
        }
    }

--------------------

### 538. 把二叉搜索树转换为累加树 ###

题目链接：[https://leetcode.cn/problems/convert-bst-to-greater-tree/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_convert-bst-to-greater-tree_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

**递归做法：**

class Solution {
        
        int sum = 0;
        public TreeNode convertBST(TreeNode root) {
        
            order(root);
            return root;
        }
    
        public void order(TreeNode root){
        
            if(root!=null){
        
                order(root.right);
                sum += root.val;
                root.val = sum;
                order(root.left);
            }
        }
    }

**非递归做法：**

class Solution {
        
        public TreeNode convertBST(TreeNode root) {
        
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode p = root;
            int sum = 0;
            while(!stack.isEmpty() || p != null){
         // 反中序遍历
                if(p!=null){
        
                    stack.push(p);
                    p = p.right;
                }else{
        
                    p = stack.pop();
                    sum += p.val;
                    p.val = sum;
                    p = p.left;
                }
            }
            return root;
        }
    }

--------------------

### 543. 二叉树的直径 ###

题目链接：[https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_diameter-of-binary-tree_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

左右节点深度加一起就是最大路径：

class Solution {
        
        int max = 0;
    
        public int diameterOfBinaryTree(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }
            maxDepth(root);
            return max;
        }
    
        public int maxDepth(TreeNode root){
        
            if(root == null){
        
                return 0;
            }
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            max = Math.max(max, leftDepth + rightDepth); // 左右节点深度加一起就是最大路径
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }

--------------------

### 617. 合并二叉树 ###

class Solution {
        
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        
            return merge(root1, root2);
        }
    
        public TreeNode merge(TreeNode root1, TreeNode root2){
        
            if(root1 == null && root2 == null){
        
                return null;
            }else if(root1 == null){
        
                return root2;
            }else if(root2 == null){
        
                return root1;
            }else{
        
                root1.val += root2.val;
                root1.left = merge(root1.left, root2.left);
                root1.right = merge(root1.right, root2.right);
                return root1;
            }
        }
    }

[https_leetcode.cn_problem-list_2cktkvj]: https://leetcode.cn/problem-list/2cktkvj/
[https_leetcode.cn_problems_binary-tree-inorder-traversal_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/binary-tree-inorder-traversal/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_binary-tree-preorder-traversal_description]: https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
[https_leetcode.cn_problems_binary-tree-postorder-traversal_description]: https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
[https_leetcode.cn_problems_unique-binary-search-trees_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/unique-binary-search-trees/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_validate-binary-search-tree_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/validate-binary-search-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_symmetric-tree_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/symmetric-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_binary-tree-level-order-traversal_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_maximum-depth-of-binary-tree_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/maximum-depth-of-binary-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_construct-binary-tree-from-preorder-and-inorder-traversal_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[-_ L2-011 _ _25_ _]: https://blog.csdn.net/weixin_43819566/article/details/110039454?ops_request_misc=&request_id=7d339465e3ba41d2ba088cddb0288faa&biz_id=&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~koosearch~default-2-110039454-null-null.268%5Ev1%5Econtrol&utm_term=%E4%BA%8C%E5%8F%89%E6%A0%91&spm=1018.2226.3001.4450
[https_leetcode.cn_problems_flatten-binary-tree-to-linked-list_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/submissions/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_binary-tree-maximum-path-sum_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/binary-tree-maximum-path-sum/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[Link 1]: https://leetcode.cn/problems/binary-tree-maximum-path-sum/solutions/18040/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-ikaruga/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_invert-binary-tree_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/invert-binary-tree/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_convert-bst-to-greater-tree_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/convert-bst-to-greater-tree/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_diameter-of-binary-tree_description_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/diameter-of-binary-tree/description/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj