代码随想录算法训练营第21天|LeetCode 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

1.LeetCode 669. 修剪二叉搜索树

题目链接：https://leetcode.cn/problems/trim-a-binary-search-tree/description/
文章链接：https://programmercarl.com/0669.修剪二叉搜索树.html
视频链接：https://www.bilibili.com/video/BV17P41177ud?share_source=copy_web

思路：
递归，利用二叉搜索树的性质，找到在区间内部的节点保留，并返回。
与二叉搜索树节点删除不同之处树是：
二叉搜索树节点删除是，利用性质，找到要删除的节点；
修剪是，利用性质，找到要保留的节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }

        if (root.val > high) { // 如果当前节点值大于high,则该节点的右边全部剪掉
            root = trimBST(root.left,low,high);
        } else if (root.val < low) {// 左边全部剪掉
            root = trimBST(root.right,low,high);
        } else {
            root.left = trimBST(root.left,low,high);
            root.right = trimBST(root.right,low,high);
        } 
    
        return root;

    }
}
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

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

题目链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
文章链接：https://programmercarl.com/0108.将有序数组转换为二叉搜索树.html
视频链接：https://www.bilibili.com/video/BV1uR4y1X7qL?share_source=copy_web

思路：
本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。
分割点就是数组中间位置的节点。
注意：
1️⃣如果数组长度为偶数，中间节点有两个，取哪一个？
取哪一个都可以，只不过构成了不同的平衡二叉搜索树。
2️⃣在构造二叉树的时候尽量不要重新定义左右区间数组，而是用下标来操作原数组。
3️⃣在定义区间的过程中遵循循环不变量，此处，我们设定区间是左闭右开。

解法：
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return find(nums,0,nums.length);
    }
    public TreeNode find(int[] nums,int start,int end) {
        if (start == end) {
            return null;
        }
        // 中
        int index = (end - start)/2 +start;
        TreeNode cur = new TreeNode(nums[index]); 
        // 切割
        int leftStart = start;
        int leftEnd = index;
        int rightStart = index + 1;
        int rightEnd = end;

        // 左
        cur.left = find(nums,leftStart,leftEnd);
        // 右
        cur.right = find(nums,rightStart,rightEnd);

        return cur;

    }
}
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
40
41
42
43
44
45

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

题目链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/description/
文章链接：https://programmercarl.com/0538.把二叉搜索树转换为累加树.html
视频链接：https://www.bilibili.com/video/BV1d44y1f7wP?share_source=copy_web

思路：
题目要求每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。又知二叉搜索树是有序的，中序遍历左中右是单调递增的。对于一个有序的数组，要求大于等于当前值的和，需要从后向前，挨个累加，就是从最大值开始分析，逐值相加，最终求和给当前位置，也就是降序分析。要想先分析最大值，则需要采用中序遍历右中左的顺序。

解法：
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        find(root);
        return root;
    }
    TreeNode pre = null;
    public void find(TreeNode cur) {
        if (cur == null) return;
        // 右
        find(cur.right);
        // 中
        if (pre != null) {
            cur.val += pre.val;
        }
        pre = cur;
        // 左
        find(cur.left);     
    }
}
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