代码随想录第二十三天

Posted on Edited on In

669 修剪二叉搜索树

给定最大边界，和最小边界，确保二叉搜索树的结点值在最大边界和最小边界之中，返回修剪好的树的节点
重构二叉树时，把给节点的父节点的左子树连接到删除之后的节点中

递归法

root小于low，就要找大于low 的值修剪右子树
root大于high，就要找小于high的值修剪左子树

root的left，就要修剪左树
root的right，修剪右树
之后返回root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    }
}

迭代法

剪枝时分三步
将root移动到L和R范围内
剪枝左子树，剪枝右子树

先找到root在L 和 R 范围中的结点
找左边的所有小于L的节点，小于L 则该节点左子树应该全部删掉，只保留右子树
找右边的所有大于R的节点，同理大于R则该节点右子树应该全部删掉，只保留左子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        while (root != null && (root.val < low || root.val > high)){
            if (root.val < low){
                root = root.right;
            } else {
                root = root.left;
            }
        }

        TreeNode cur = root;

        while (cur != null){
            while (cur.left != null && cur.left.val < low){
                cur.left = cur.left.right;
            }

            cur = cur.left;
        }

        cur = root;

        while (cur != null){
            while (cur.right != null && cur.right.val > high){
                cur.right = cur.right.left;
            }

            cur = cur.right;
        }

        return root;
    }
}

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

递归分数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildHelper(nums, 0, nums.length);
    }

    private TreeNode buildHelper(int[] nums, int start, int end){
        if (start >= end) return null;
        int midIndex = start + ((end - start) >> 1);
        int midValue = nums[midIndex];

        TreeNode root = new TreeNode(midValue);

        root.left = buildHelper(nums, start, midIndex);
        root.right = buildHelper(nums, midIndex + 1, end);

        return root;
    }
}

538 把二叉搜索树转换成累加树

题目里是右中左的顺序，也就是反中序遍历变换而成的累加树

在递归中添加sum累加node的值，在赋给root的值上

最后遍历整个树就会获得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;

        root.right = convertBST(root.right);

        sum += root.val;
        root.val = sum;

        root.left = convertBST(root.left);
        return root;
    }
}

复习

二叉树深度遍历

递归
后序为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return result;

        postorder(root);

        return result;
    }

    private void postorder(TreeNode root){
        if (root == null) return;

        postorder(root.left);
        postorder(root.right);
        result.add(root.val);
    }
}

迭代
前序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return result;
    }
}

中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()){
            if (cur != null){
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }

        return result;
    }
}

后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        Collections.reverse(result);
        return result;
    }
}

统一迭代
后序为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                stack.push(node);
                stack.push(null);
                if (node.right != null) stack.push(node.right);
                if (node.left != null) stack.push(node.left);
            } else {
                result.add(stack.pop().val);
            }
        }
        return result;
    }
}

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return result;

        dfs(root, 0);

        return result;
    }

    private void dfs(TreeNode root, int depth){
        if (root == null) return;
        depth++;
        if (depth > result.size()){
            result.add(new ArrayList<Integer>());
        }

        result.get(depth - 1).add(root.val);

        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right, depth);
    }
}

二叉树层序遍历

bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> item = new ArrayList<>();
            int length = queue.size();

            while (length-- > 0){
                TreeNode node = queue.poll();
                
                item.add(node.val);

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }

            result.add(item);
        }

        return result;
    }
}

226 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;

        swapChildren(root);

        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    private void swapChildren(TreeNode node){
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

101 对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;

        boolean compareOutside = compare(left.left, right.right);
        boolean compareInside = compare(left.right,right.left);

        return compareOutside && compareInside;
    }
}

104 二叉树最大深度

1
2
3
4
5
6
7
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;

        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

111 二叉树最小深度

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int minDepth = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        dfs(root,0);
        return minDepth;
    }

    private void dfs(TreeNode root, int depth){
        depth++;
        if (root.left == null && root.right == null){
            if (depth < minDepth){
                minDepth = depth;
            }
        }

        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right,depth);
    }
}

层序迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()){
            int length = queue.size();
            depth++;
            while(length-- > 0){
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) return depth;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }

        return depth;
    }
}

222 完全二叉树节点个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;

        TreeNode left = root.left;
        TreeNode right = root.right;

        int leftDepth = 0;
        int rightDepth = 0;
        while (left != null){
            left = left.left;
            leftDepth++;
        }

        while(right != null){
            right = right.right;
            rightDepth++;
        }

        if (leftDepth == rightDepth){
            return (2 << leftDepth) - 1;
        }

        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

110 平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    public int getHeight(TreeNode root){
        if (root == null) return 0;

        int left = getHeight(root.left);
        if (left == -1) return -1;
        int right = getHeight(root.right);
        if (right == -1) return -1;
    
        if (Math.abs(left - right) > 1){
            return -1;
        }

        return 1 + Math.max(left, right);
    }
}

257 二叉树的所有路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    List<String> result = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) return result;
        List<Integer> paths = new ArrayList<>();
        getPaths(root, paths);
        return result;
    }

    private void getPaths(TreeNode root, List<Integer> paths){
        paths.add(root.val);
        if (root.left == null && root.right == null){
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < paths.size() - 1; i++){
                sb.append(paths.get(i)).append("->");
            }   

            sb.append(paths.get(paths.size() - 1));

            result.add(sb.toString());
            return;
        }

        if (root.left != null){
            getPaths(root.left, paths);
            paths.remove(paths.size() - 1);
        }
        if (root.right != null){
            getPaths(root.right, paths);
            paths.remove(paths.size() - 1);
        }
    }
}

404 左叶子之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return sum;
        dfs(root, 0);
        return sum;
    }

    private void dfs(TreeNode root, int depth){
        depth++;
        if (root.left != null && root.left.left == null && root.left.right == null){
            sum += root.left.val;
        }

        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right, depth);
    }
}

简便写法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if (root.left != null && root.left.left == null && root.left.right == null){
            sum += root.left.val;
        }
        if (root.left != null) sumOfLeftLeaves(root.left);
        if (root.right != null) sumOfLeftLeaves(root.right);

        return sum;
    }
}

513 找树左下角的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int maxDepth = 0;
    int result = 0;
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return result;
        dfs(root, 0);
        return result;
    }

    private void dfs(TreeNode root, int depth){
        depth++;

        if (root.left == null && root.right == null && depth > maxDepth){
            result = root.val;
            maxDepth = depth;
        }

        if (root.left != null) dfs(root.left, depth);
        if (root.right != null) dfs(root.right, depth);
    }
}

112 路径总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        return getPaths(root, targetSum);
    }

    private boolean getPaths(TreeNode root, int targetSum){
        if (root == null) return false;
        targetSum -= root.val;

        if (root.left == null && root.right == null){
            if (targetSum == 0) return true;
            else return false;
        }

        boolean left = getPaths(root.left, targetSum);
        boolean right = getPaths(root.right, targetSum);

        return left || right;
    }
}

113 路径总和II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return result;

        List<Integer> path = new ArrayList<>();

        getPath(root, targetSum, path);

        return result;
    }

    private void getPath(TreeNode root, int targetSum, List<Integer> path){
        path.add(root.val);
        targetSum -= root.val;

        if (root.left == null && root.right == null){
            if (targetSum == 0){
                result.add(new ArrayList<Integer>(path));
                return;
            }
        }

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;
        int count = 0;
        for (int i : inorder){
            map.put(i, count++);
        }
        return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode buildHelper(int[] inorder, int inS, int inE, int[] postorder, int postS, int postE){
        if (inS >= inE || postS >= postE) return null;
        int rootVal = postorder[postE - 1];
        int rootIndex = map.get(rootVal);
        int lenOfLeft = rootIndex - inS;
        TreeNode root = new TreeNode(rootVal);

        root.left = buildHelper(inorder, inS, rootIndex, postorder, postS, postS + lenOfLeft);
        root.right = buildHelper(inorder, rootIndex + 1, inE, postorder, postS + lenOfLeft, postE - 1);

        return root;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (inorder.length == 0) return null;
        int count = 0;
        for (int i : inorder){
            map.put(i, count++);
        }
        return buildHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildHelper(int[] preorder, int preS, int preE, int[] inorder, int inS, int inE){
        if (preS >= preE || inS >= inE) return null;
        int rootVal = preorder[preS];
        int rootIndex = map.get(rootVal);
        int lenOfLeft = rootIndex - inS;
        TreeNode root = new TreeNode(rootVal);

        root.left = buildHelper(preorder, preS + 1, preS + 1 + lenOfLeft, inorder, inS, rootIndex);
        root.right = buildHelper(preorder, preS + 1 + lenOfLeft, preE, inorder, rootIndex + 1, inE);

        return root;
    }
}

654 最大二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums){
        if (nums.length == 0) return null;
        return buildHelper(nums, 0, nums.length);
    }

    private int[] getMaximum(int[] nums, int start, int end){
        int[] result = new int[2];
        result[0] = Integer.MIN_VALUE;
        result[1] = -1;
        for (int i = start; i < end; i++){
            if (nums[i] > result[0]){
                result[0] = nums[i];
                result[1] = i;
            }
        }
        return result;
    }

    private TreeNode buildHelper(int[] nums, int start, int end){
        if (start >= end) return null;
        int[] maxArray = getMaximum(nums, start, end);
        int rootVal = maxArray[0];
        int rootIndex = maxArray[1];

        TreeNode root = new TreeNode(rootVal);

        root.left = buildHelper(nums, start, rootIndex);
        root.right = buildHelper(nums, rootIndex + 1, end);

        return root;
    }
}

617 合并二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return null;
        if (root1 == null && root2 != null) return root2;
        if (root1 != null && root2 == null) return root1;
        TreeNode root = new TreeNode(root1.val + root2.val);
        

        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);

        return root;  
    }
}

700 二叉搜索树中的搜索

1
2
3
4
5
6
7
8
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;
        else if (root.val > val) return searchBST(root.left, val);
        else return searchBST(root.right, val);
    }
}

98 验证二叉搜索树

注意对比返回left的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    TreeNode pre;
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        boolean left = isValidBST(root.left);
        if (!left) return false;
        
        if (pre != null && pre.val >= root.val) return false;
        pre = root;

        boolean right = isValidBST(root.right);

        return right;
    }
}

107 二叉树的层次遍历II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){
            int length = queue.size();
            List<Integer> item = new ArrayList<>();
            while(length-- > 0){
                TreeNode node = queue.poll();
                item.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(item);
        }

        Collections.reverse(result);

        return result;
    }
}

199 二叉树的右视图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){
            int length = queue.size();
            while(length-- > 0){
                TreeNode node = queue.poll();
                if (length == 0){
                    result.add(node.val);
                }

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        
        return result;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    TreeNode pre;
    int minDiff = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;

        getMinimumDifference(root.left);
        if (pre != null && root.val - pre.val < minDiff){
            minDiff = root.val - pre.val;
        }

        pre = root;

        getMinimumDifference(root.right);

        return minDiff;
    }
}

501 二叉搜索树中的众数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    int maxCount = 0;
    int count = 0;
    List<Integer> result = new ArrayList<>();
    TreeNode pre;

    public int[] findMode(TreeNode root) {
        inorder(root);
        int[] res = new int[result.size()];
        int count = 0;
        for (int i : result){
            res[count++] = i;
        }

        return res;
    }

    private void inorder(TreeNode root){
        if (root == null) return;
        inorder(root.left);

        if (pre == null || pre.val != root.val){
            count = 1;
        } else {
            count++;
        }

        if (maxCount < count){
            result.clear();
            result.add(root.val);
            maxCount = count;
        } else if (count == maxCount){
            result.add(root.val);
        }

        pre = root;
        inorder(root.right);
    }
}

236 二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);

        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left == null && right != null) return right;
        else if (left != null && right == null) return left;
        else if (left != null && right != null) return root;
        else return null;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        
        if (p.val > q.val){
            TreeNode temp = p;
            p = q;
            q = temp;
        }

        if (root.val >= p.val && root.val <= q.val) return root;
        else if (root.val < p.val) return lowestCommonAncestor(root.right, p, q);
        else return lowestCommonAncestor(root.left, p, q);
    }
}

701 二叉搜索树中插入

1
2
3
4
5
6
7
8
9
10
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 删除二叉搜索树中的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;

        if (root.val == key){
            if (root.left == null) return root.right;
            else if (root.right == null) return root.left;
            else {
                TreeNode cur = root.right;
                while (cur.left != null){
                    cur = cur.left;
                }

                cur.left = root.left;
                root = root.right;

                return root;
            }
        }

        if (root.val < key) root.right = deleteNode(root.right, key);
        if (root.val > key) root.left = deleteNode(root.left, key);
        return root;
    }
}


669 修剪二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
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 将有序数组转换为二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        return buildHelper(nums, 0, nums.length);
    }
    private TreeNode buildHelper(int[] nums, int start, int end){
        if (start >= end) return null;
        int midIndex = start + ((end - start) >> 1);
        int midValue = nums[midIndex];

        TreeNode root = new TreeNode(midValue);

        root.left = buildHelper(nums, start, midIndex);
        root.right = buildHelper(nums, midIndex + 1, end);

        return root;
    }
}

538 把二叉搜索树转换成累加树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {

    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        return revertInorder(root);
    }

    private TreeNode revertInorder(TreeNode root){
        if (root == null) return null;
        revertInorder(root.right);
        sum += root.val;
        root.val = sum;
        revertInorder(root.left);

        return root;
    }
}