二叉树 | Bgemini

144.二叉树的前序遍历

题目：

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

1 2	输入：root = [1,null,2,3] 输出：[1,2,3]

示例 2：

1 2	输入：root = [] 输出：[]

示例 3：

1 2	输入：root = [1] 输出：[1]

示例 4：

1 2	输入：root = [1,2] 输出：[1,2]

示例 5：

1 2	输入：root = [1,null,2] 输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

代码：

（递归法）

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root,res);
        return res;
    }

    public void preorder(TreeNode root,List<Integer> res){
        if(root == null){
            return;
        }
        res.add(root.val);
        preorder(root.left,res);
        preorder(root.right,res);
    }
}

（迭代法）

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }
        return res;
    }
}

145.二叉树的后序遍历

题目：

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

1 2	输入：root = [1,null,2,3] 输出：[3,2,1]

示例 2：

1 2	输入：root = [] 输出：[]

示例 3：

1 2	输入：root = [1] 输出：[1]

提示：

树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

代码：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root,res);
        return res;
    }

    public void postorder(TreeNode root,List<Integer> res){
        if(root == null){
            return;
        }
        postorder(root.left,res);
        postorder(root.right,res);
        res.add(root.val);
    }
}

（迭代法）

94.二叉树的中序遍历

题目：

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

示例 1：

1 2	输入：root = [1,null,2,3] 输出：[1,3,2]

示例 2：

1 2	输入：root = [] 输出：[]

示例 3：

1 2	输入：root = [1] 输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

代码：

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

102.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：

1 2	输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]

示例 2：

1 2	输入：root = [1] 输出：[[1]]

示例 3：

1 2	输入：root = [] 输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

代码：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resList = new ArrayList<>();
        if(root == null){
            return resList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> itemList = new LinkedList<>();
            int size = queue.size();   //记录每层的个数

            while(size -- > 0){
                TreeNode tmpNode = queue.poll();
                itemList.add(tmpNode.val);

                if(tmpNode.left != null){
                    queue.add(tmpNode.left);
                }
                if(tmpNode.right != null){
                    queue.add(tmpNode.right);
                }
            }
            resList.add(itemList);
        }
        return resList;
    }
}

（代码抽取函数版本）

class Solution {
    public List<List<Integer>> resList = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        checkFun(root);
        return resList;
    }

    public void checkFun(TreeNode node){
        if(node == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while(!queue.isEmpty()){
            List<Integer> itemList = new LinkedList<>();
            int size = queue.size();   //记录每层的个数

            while(size -- > 0){
                TreeNode tmpNode = queue.poll();
                itemList.add(tmpNode.val);

                if(tmpNode.left != null){
                    queue.add(tmpNode.left);
                }
                if(tmpNode.right != null){
                    queue.add(tmpNode.right);
                }
            }
            resList.add(itemList);
        }
    }
}

107.二叉树的层次遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

1 2	输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]

示例 2：

1 2	输入：root = [1] 输出：[[1]]

示例 3：

1 2	输入：root = [] 输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

代码：

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> resList = new ArrayList<>();
        if(root == null){
            return resList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> itemList = new LinkedList<>();
            int size = queue.size();   //记录每层的个数

            while(size -- > 0){
                TreeNode tmpNode = queue.poll();
                itemList.add(tmpNode.val);

                if(tmpNode.left != null){
                    queue.add(tmpNode.left);
                }
                if(tmpNode.right != null){
                    queue.add(tmpNode.right);
                }
            }
            resList.add(itemList);
        }
        //只需要翻转一下就可以了
        List<List<Integer>> res = new LinkedList<>();
        for(int i = resList.size() - 1;i >= 0;i --){
            res.add(resList.get(i));
        }
        return res;
    }
}

199.二叉树的右视图

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

示例 1:

1 2	输入: [1,2,3,null,5,null,4] 输出: [1,3,4]

示例 2:

1 2	输入: [1,null,3] 输出: [1,3]

示例 3:

1 2	输入: [] 输出: []

提示:

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

代码：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            /*
            for(int i = 0;i < size;i ++){
                TreeNode tmp = queue.poll();
                if(tmp.left != null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
                if(i == size - 1){
                    res.add(tmp.val);
                }
            }
            */
            while(size -- > 0){
                TreeNode tmp = queue.poll();
                if(tmp.left != null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
                if(size == 0){
                    res.add(tmp.val);
                }
            }
        }
        return res;
    }
}

637.二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

示例 2:

1 2	输入：root = [3,9,20,15,7] 输出：[3.00000,14.50000,11.00000]

提示：

树中节点数量在 [1, 104] 范围内
-231 <= Node.val <= 231 - 1

代码：

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            double sum = 0.0;
            for(int i = 0;i < size;i ++){
                TreeNode tmp = queue.poll();
                sum += tmp.val;
                if(tmp.left != null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
            }
            res.add(sum/size);
        }
        return res;
    }
}

429.N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

1 2	输入：root = [1,null,3,2,4,null,5,6] 输出：[[1],[3,2,4],[5,6]]

示例 2：

1 2	输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

树的高度不会超过 1000
树的节点总数在 [0, 104] 之间

代码：

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> itemList = new LinkedList<>();
            int size = queue.size();
            for(int i = 0;i < size;i ++){
                Node tmp = queue.poll();
                itemList.add(tmp.val);

                List<Node> children = tmp.children;
                if(children == null || children.size() == 0){
                    continue;
                }
                for(Node child : children){
                    if(child != null){
                        queue.add(child);
                    }
                }

            }
            res.add(itemList);
        }
        return res;
    }
}

515.在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

1 2	输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]

示例2：

1 2	输入: root = [1,2,3] 输出: [1,3]

提示：

二叉树的节点个数的范围是 [0,104]
-231 <= Node.val <= 231 - 1

代码：

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            for(int i = 0;i < size;i ++){
                TreeNode tmp = queue.poll();
                max = Math.max(max,tmp.val);
                if(tmp.left != null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
            }
            res.add(max);
        }
        return res;
    }
}

116.填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例 1：

1
2
3

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

1 2	输入：root = [] 输出：[]

提示：

树中节点的数量在 [0, 212 - 1] 范围内
-1000 <= node.val <= 1000

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

代码：

class Solution {
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<>();
        if(root == null){
            return root;
        }
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i < size;i ++){
                Node tmp = queue.poll();
                if(i < size - 1){
                    tmp.next = queue.peek();
                }
                if(tmp.left != null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
            }
        }
        return root;
    }
}

117.填充每个节点的下一个右侧节点指针II

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

1
2
3

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例 2：

1 2	输入：root = [] 输出：[]

提示：

树中的节点数在范围 [0, 6000] 内
-100 <= Node.val <= 100

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。

代码：

class Solution {
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<>();
        if(root == null){
            return root;
        }
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            Node pre = null;
            Node tmp = null;
            for(int i = 0;i < size;i ++){
                if(i == 0){
                    pre = queue.poll();
                    tmp = pre;
                }else{
                    tmp = queue.poll();
                    pre.next = tmp;
                    pre = pre.next;
                }
                if(tmp.left != null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
            }
            pre.next = null;
        }
        return root;
    }
}

104.二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

1 2	输入：root = [3,9,20,null,null,15,7] 输出：3

示例 2：

1 2	输入：root = [1,null,2] 输出：2

提示：

树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100

代码：

（后序递归）

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

（层序迭代）

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

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

示例 1：

1 2	输入：root = [3,9,20,null,null,15,7] 输出：2

示例 2：

1 2	输入：root = [2,null,3,null,4,null,5,null,6] 输出：5

提示：

树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000

代码：

（后序递归）

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHight = minDepth(root.left);
        int rightHight = minDepth(root.right);
        if(root.left != null && root.right == null){
            return 1 + leftHight;
        }
        if(root.left == null && root.right != null){
            return 1 + rightHight;
        }
        return 1 + Math.min(leftHight,rightHight);
    }
}

（层序迭代）

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        int depth = 0;
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            depth ++;
            while(size -- > 0){
                TreeNode tmp = queue.poll();
                if(tmp.left == null && tmp.right == null){
                    return depth;
                }
                if(tmp.left != null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
            }
        }
        return depth;
    }
}

226.翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

1 2	输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]

示例 2：

1 2	输入：root = [2,1,3] 输出：[2,3,1]

示例 3：

1 2	输入：root = [] 输出：[]

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

代码：

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

    public void swap(TreeNode root){
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

1 2	输入：root = [1,2,2,3,4,4,3] 输出：true

示例 2：

1 2	输入：root = [1,2,2,null,3,null,3] 输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

代码：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left,root.right);
    }

    private boolean compare(TreeNode left,TreeNode right){
        if(left == null && right == null){
            return true;
        }
        if(left == null && right != null){
            return false;
        } 
        if(left != null && right == null){
            return false;
        }
        if(left.val != right.val){
            return false;
        }
        boolean outside = compare(left.left,right.right);
        boolean inside = compare(left.right,right.left);
        return outside && inside;

    }
}

222.完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：

1 2	输入：root = [1,2,3,4,5,6] 输出：6

示例 2：

1 2	输入：root = [] 输出：0

示例 3：

1 2	输入：root = [1] 输出：1

提示：

树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

代码：

（后序递归）

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftNum = countNodes(root.left);
        int rightNum = countNodes(root.right);
        return leftNum + rightNum + 1;
    }
}

（层序迭代法）

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int res = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i < size;i ++){
                TreeNode tmp = queue.poll();
                res ++;
                if(tmp.left != null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
            }
        }
        return res;
    }
}

（利用完全二叉树特性）

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0;
        while(left != null){
            left = left.left;
            leftDepth ++;
        }
        while(right != null){
            right = right.right;
            rightDepth ++;
        }
        if(leftDepth == rightDepth){
            return (2 << leftDepth) - 1;
        }
        int getLeft = countNodes(root.left);
        int getRight = countNodes(root.right);
        return getLeft + getRight + 1;
    }
}

110.平衡二叉树

给定一个二叉树，判断它是否是

平衡二叉树

示例 1：

1 2	输入：root = [3,9,20,null,null,15,7] 输出：true

示例 2：

1 2	输入：root = [1,2,2,3,3,null,null,4,4] 输出：false

示例 3：

1 2	输入：root = [] 输出：true

提示：

树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

代码：

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }
    private int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if(leftHeight == -1){
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if(rightHeight == -1){
            return -1;
        }
        if(Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }else{
            return Math.max(leftHeight,rightHeight) + 1;
        }

    }
}

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

1 2	输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]

示例 2：

1 2	输入：root = [1] 输出：["1"]

提示：

树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100

代码：

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        List<Integer> path = new ArrayList<>();
        traversal(root,path,res);
        return res;
    }

    private void traversal(TreeNode root,List<Integer> path,List<String> res){
        path.add(root.val);
        if(root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i < path.size() - 1;i ++){
                sb.append(path.get(i)).append("->");
            }
            sb.append(path.get(path.size() - 1));
            res.add(sb.toString());
            return;
        }

        if(root.left != null){
            traversal(root.left,path,res);
            path.remove(path.size() - 1);
        }
        if(root.right != null){
            traversal(root.right,path,res);
            path.remove(path.size() - 1);
        }
    }
}

404.左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

1
2
3

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

1 2	输入: root = [1] 输出: 0

提示:

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000

代码：

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftNum = sumOfLeftLeaves(root.left);
        int rightNum = sumOfLeftLeaves(root.right);
        int tmp = 0;
        if(root.left != null && root.left.left == null && root.left.right == null){
            tmp = root.left.val;
        }
        int sum = tmp + leftNum + rightNum;
        return sum;
    }
}

513.找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

1 2	输入: root = [2,1,3] 输出: 1

示例 2:

1 2	输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7

提示:

二叉树的节点个数的范围是 [1,104]
-231 <= Node.val <= 231 - 1

代码：

（递归法）

class Solution {
    private int res = 0;
    private int maxDepth = Integer.MIN_VALUE;
    public int findBottomLeftValue(TreeNode root) {
        res = root.val;
        traversal(root,0);
        return res;
    }

    private void traversal(TreeNode root,int depth){
        if(root == null) return;
        if(root.left == null && root.right == null){
            if(depth > maxDepth){
                maxDepth = depth;
                res = root.val;
            }
        }
        if(root.left != null){
            traversal(root.left,depth + 1);
        }
        if(root.right != null){
            traversal(root.right,depth + 1);
        }
    }
}

（层序迭代法）

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int res = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i < size;i ++){
                TreeNode tmp = queue.poll();
                if(i == 0){
                    res = tmp.val;
                }
                if(tmp.left != null){
                    queue.add(tmp.left);
                }
                if(tmp.right != null){
                    queue.add(tmp.right);
                }
            }
        }
        return res;
    }
}

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：

1
2
3

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

1
2
3

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

代码：

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        targetSum -= root.val;
        if(root.left == null && root.right == null){
            return targetSum == 0;
        }
        if(root.left != null){
            if(hasPathSum(root.left,targetSum)){
                return true;
            }
        }
        if(root.right != null){
            if(hasPathSum(root.right,targetSum)){
                return true;
            }
        }
        return false;
    }
}

113. 路径总和II

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

叶子节点 是指没有子节点的节点。

示例 1：

1 2	输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

1 2	输入：root = [1,2,3], targetSum = 5 输出：[]

示例 3：

1 2	输入：root = [1,2], targetSum = 0 输出：[]

提示：

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

代码：

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        List<Integer> path = new LinkedList<>();
        find(root,targetSum,res,path);
        return res;
    }

    public void find(TreeNode root,int targetSum,List<List<Integer>> res,List<Integer> path){
        path.add(root.val);
        if(root.left == null && root.right == null){
            if(targetSum - root.val == 0){
                res.add(new ArrayList<>(path));
            }
            return;
        }
        if(root.left != null){
            find(root.left,targetSum - root.val,res,path);
            path.remove(path.size() - 1);
        }
        if(root.right != null){
            find(root.right,targetSum - root.val,res,path);
            path.remove(path.size() - 1);
        }
    }
}

106.从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

1 2	输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]

示例 2:

1 2	输入：inorder = [-1], postorder = [-1] 输出：[-1]

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由不同的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

代码：

class Solution {
    Map<Integer,Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for(int i = 0;i < inorder.length;i ++){
            map.put(inorder[i],i);
        }
        return findNode(inorder,0,inorder.length,postorder,0,postorder.length);
    }
    
    public TreeNode findNode(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){
        //参数范围都是左闭右开
        if(inBegin >= inEnd || postBegin >= postEnd){
            return null;
        }
        // 找到后序遍历的最后一个元素在中序遍历中的位置
        int rootIndex = map.get(postorder[postEnd - 1]);
        // 构造结点
        TreeNode root = new TreeNode(inorder[rootIndex]);
        // 保存中序左子树个数
        int lenOfLeft = rootIndex - inBegin;
        root.left = findNode(inorder,inBegin,rootIndex,postorder,postBegin,postBegin + lenOfLeft);
        root.right = findNode(inorder,rootIndex + 1,inEnd,postorder,postBegin + lenOfLeft,postEnd - 1);
        return root;
    }
}

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

1 2	输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]

示例 2:

1 2	输入: preorder = [-1], inorder = [-1] 输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

代码：

class Solution {
    Map<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for(int i = 0;i < inorder.length;i ++){
            map.put(inorder[i],i);
        }
        return findNode(preorder,0,preorder.length,inorder,0,inorder.length);
    }

    public TreeNode findNode(int[] preorder,int preBegin,int preEnd,int[] inorder,int inBegin,int inEnd){
        if(preBegin >= preEnd || inBegin >= inEnd){
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);
        TreeNode root = new TreeNode(inorder[rootIndex]);
        int lenOfleft = rootIndex - inBegin;
        root.left = findNode(preorder,preBegin + 1,preBegin + lenOfleft + 1,inorder,inBegin,rootIndex);
        root.right = findNode(preorder,preBegin + lenOfleft + 1,preEnd,inorder,rootIndex + 1,inEnd);
        return root;
    }
}

654.最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。

返回 nums 构建的 *最大二叉树* 。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

1 2	输入：nums = [3,2,1] 输出：[3,null,2,null,1]

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同

代码：

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums,0,nums.length);
    }

    public TreeNode construct(int[] nums,int leftIndex,int rightIndex){
        if(rightIndex - leftIndex < 1){
            return null;
        }
        if(rightIndex - leftIndex == 1){
            return new TreeNode(nums[leftIndex]);
        }
        int maxIndex = leftIndex;
        int maxValue = nums[maxIndex];
        for(int i = leftIndex + 1;i < rightIndex;i ++){
            if(nums[i] > maxValue){
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxValue);
        root.left = construct(nums,leftIndex,maxIndex);
        root.right = construct(nums,maxIndex + 1,rightIndex);
        return root;
    }
}

617.合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

1 2	输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输出：[3,4,5,5,4,null,7]

示例 2：

1 2	输入：root1 = [1], root2 = [1,2] 输出：[2,2]

提示：

两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104

代码：

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

700.二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

示例 1:

1 2	输入：root = [4,2,7,1,3], val = 2 输出：[2,1,3]

示例 2:

1 2	输入：root = [4,2,7,1,3], val = 5 输出：[]

提示：

树中节点数在 [1, 5000] 范围内
1 <= Node.val <= 107
root 是二叉搜索树
1 <= val <= 107

代码：

（递归法）

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val) return root;
        if(val < root.val){
            return searchBST(root.left,val);
        }else{
            return searchBST(root.right,val);
        }
    }
}

（迭代法）

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root != null){
            if(val < root.val){
                root = root.left;
            }else if(val > root.val){
                root = root.right;
            }else{
                return root;
            }
        }
        return null;
    }
}

98.验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

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

示例 1：

1 2	输入：root = [2,1,3] 输出：true

示例 2：

1
2
3

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

代码：

class Solution {
    TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        boolean left = isValidBST(root.left);
        if(pre!= null && pre.val >= root.val){
            return false;
        }
        pre = root;
        boolean right = isValidBST(root.right);
        return left && right;
    }
}

530.二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

1 2	输入：root = [4,2,6,1,3] 输出：1

示例 2：

1 2	输入：root = [1,0,48,null,null,12,49] 输出：1

提示：

树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105

代码：

class Solution {
    TreeNode pre;
    int res = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        traversal(root);
        return res;
    }

    public void traversal(TreeNode root){
        if(root == null) return;
        traversal(root.left);
        if(pre != null){
            res = Math.min(res,root.val - pre.val);
        }
        pre = root;
        traversal(root.right);
    }
}

501.二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：

1 2	输入：root = [1,null,2,2] 输出：[2]

示例 2：

1 2	输入：root = [0] 输出：[0]

提示：

树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

代码：

class Solution {
    int maxCount;
    int count;
    ArrayList<Integer> resList;
    TreeNode pre;
    public int[] findMode(TreeNode root) {
        resList = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        traversal(root);
        int[] res = new int[resList.size()];
        for(int i = 0;i < resList.size();i ++){
            res[i] = resList.get(i);
        }
        return res;
    }

    public void traversal(TreeNode root){
        if(root == null) return;
        traversal(root.left);
        if(pre == null){
            count = 1;
        }else if(pre.val == root.val){
            count ++;
        }else{
            count = 1;
        }
        if(count > maxCount){
            resList.clear();
            resList.add(root.val);
            maxCount = count;
        }else if(count == maxCount){
            resList.add(root.val);
        }
        pre = root;
        traversal(root.right);
    }
}

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

1
2
3

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

1
2
3

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

1 2	输入：root = [1,2], p = 1, q = 2 输出：1

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

代码：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left == null && right == null){
            return null;
        }else if(left == null && right != null){
            return right;
        }else if(left != null && right == null){
            return left;
        }else{
            return root;
        }
    }
}

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

1
2
3

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

1
2
3

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

代码：

（递归法）

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root.val > p.val && root.val > q.val){
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            if(left != null) return left;
        }
        if(root.val < p.val && root.val < q.val){
            TreeNode right = lowestCommonAncestor(root.right,p,q);
            if(right != null) return right;
        }
        return root;
    }
}

（迭代法）

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(true){
            if(root.val > p.val && root.val > q.val){
                root = root.left;
            }else if(root.val < p.val && root.val < q.val){
                root = root.right;
            }else{
                break;
            }
        }
        return root;
    }
}

701.二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回 任意有效的结果 。

示例 1：

1
2
3

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

1 2	输入：root = [40,20,60,10,30,50,70], val = 25 输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

1 2	输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 输出：[4,2,7,1,3,5]

提示：

树中的节点数将在 [0, 104]的范围内。
-108 <= Node.val <= 108
所有值 Node.val 是 独一无二 的。
-108 <= val <= 108
保证 val 在原始BST中不存在。

代码：

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            return new TreeNode(val);
        }
        if(root.val < val){
            root.right = insertIntoBST(root.right,val);
        }
        if(root.val > val){
            root.left = insertIntoBST(root.left,val);
        }
        return root;
    }
}

450.删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

1
2
3

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

1 2	输入: root = [], key = 0 输出: []

提示:

节点数的范围 [0, 104].
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105

进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。

代码：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;
        if(root.val == key){   //找到要删除的节点
            if(root.left == null && root.right == null){   //左孩子右孩子都空，即叶子节点
                return null;
            }
            if(root.left == null && root.right != null){   //左孩子空右孩子不空
                return root.right;
            }else if(root.right == null && root.left != null){  //左孩子不空右孩子空
                return root.left;
            }else{    //左右孩子都不空
                TreeNode cur = root.right;
                while(cur.left != null){
                    cur = cur.left;
                }
                cur.left = root.left;
                return root.right;
            }
        }
        if(root.val > key){
            root.left = deleteNode(root.left,key);
        }
        if(root.val < key){
            root.right = deleteNode(root.right,key);
        }
        return root;
    }
}

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：

1 2	输入：root = [1,0,2], low = 1, high = 2 输出：[1,null,2]

示例 2：

1 2	输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输出：[3,2,null,1]

提示：

树中节点数在范围 [1, 104] 内
0 <= Node.val <= 104
树中每个节点的值都是唯一的
题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 104

代码：

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) return null;
        if(root.val < low){
            return trimBST(root.right,low,high);
        }
        if(root.val > high){
            return trimBST(root.left,low,high);
        }
        root.left = trimBST(root.left,low,high);
        root.right = trimBST(root.right,low,high);
        return root;
    }
}

108.将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵

平衡

二叉搜索树。

示例 1：

1
2
3

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

1
2
3

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

代码：

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return traversal(nums,0,nums.length - 1);
    }
    public TreeNode traversal(int[] nums,int left,int right){
        if(left > right){
            return null;
        }
        int mid = left + ((right - left) >> 1);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = traversal(nums,left,mid - 1);
        root.right = traversal(nums,mid + 1,right);
        return root;
    }
}

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

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

1 2	输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

1 2	输入：root = [0,null,1] 输出：[1,null,1]

示例 3：

1 2	输入：root = [1,0,2] 输出：[3,3,2]

示例 4：

1 2	输入：root = [3,2,4,1] 输出：[7,9,4,10]

提示：

树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

代码：

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