代码随想录算法训练营第二十三天 |669. 修剪二叉搜索树，108.将有序数组转换为二叉搜索树，538.把二叉搜索树转换为累加树（待补充）

傷城~ 2024-04-23 04:09 64阅读 0赞

### 669.修剪二叉搜索树 ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在\[L, R\]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

![083a1e889ef9adb6bf908d217a29ca9f.png][]

![a995d38083247583827ea073a586d2fd.png][]

4、视频链接：

[你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树\_哔哩哔哩\_bilibili][LeetCode_669. _bilibili]

5、思路：

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在[low,high]范围内
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);
            return root;
        }
    }

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 curr = root;
    
            //deal with root's left sub-tree, and deal with the value smaller than low.
            while(curr != null){
                while(curr.left != null && curr.left.val < low){
                    curr.left = curr.left.right;
                }
                curr = curr.left;
            }
            //go back to root;
            curr = root;
    
            //deal with root's righg sub-tree, and deal with the value bigger than high.
            while(curr != null){
                while(curr.right != null && curr.right.val > high){
                    curr.right = curr.right.left;
                }
                curr = curr.right;
            }
            return root;
        }
    }

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

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

![944edc2fb3cf82bd5f980fee43b2cce9.png][]

4、视频链接：

[构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树\_哔哩哔哩\_bilibili][LeetCode_108._bilibili]

5、思路：

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

class Solution {
    	public TreeNode sortedArrayToBST(int[] nums) {
    		TreeNode root = traversal(nums, 0, nums.length - 1);
    		return root;
    	}
    
    	// 左闭右闭区间[left, right]
    	private 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;
    	}
    }

class Solution {
    	public TreeNode sortedArrayToBST(int[] nums) {
    		if (nums.length == 0) return null;
    
    		//根节点初始化
    		TreeNode root = new TreeNode(-1);
    		Queue<TreeNode> nodeQueue = new LinkedList<>();
    		Queue<Integer> leftQueue = new LinkedList<>();
    		Queue<Integer> rightQueue = new LinkedList<>();
    
    		// 根节点入队列
    		nodeQueue.offer(root);
    		// 0为左区间下标初始位置
    		leftQueue.offer(0);
    		// nums.size() - 1为右区间下标初始位置
    		rightQueue.offer(nums.length - 1);
    
    		while (!nodeQueue.isEmpty()) {
    			TreeNode currNode = nodeQueue.poll();
    			int left = leftQueue.poll();
    			int right = rightQueue.poll();
    			int mid = left + ((right - left) >> 1);
    
    			// 将mid对应的元素给中间节点
    			currNode.val = nums[mid];
    
    			// 处理左区间
    			if (left <= mid - 1) {
    				currNode.left = new TreeNode(-1);
    				nodeQueue.offer(currNode.left);
    				leftQueue.offer(left);
    				rightQueue.offer(mid - 1);
    			}
    
    			// 处理右区间
    			if (right >= mid + 1) {
    				currNode.right = new TreeNode(-1);
    				nodeQueue.offer(currNode.right);
    				leftQueue.offer(mid + 1);
    				rightQueue.offer(right);
    			}
    		}
    		return root;
    	}
    }

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

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 2]

2、文章讲解：[代码随想录][Link 3]

3、题目：

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

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

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

示例 1：

![ab734b4161d2dd6e091702ccea418175.png][]

*  输入：\[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：

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

示例 3：

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

示例 4：

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

提示：

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

4、思路：

5、视频链接：[普大喜奔！二叉树章节已全部更完啦！| LeetCode：538.把二叉搜索树转换为累加树\_哔哩哔哩\_bilibili][LeetCode_538._bilibili]

class Solution {
        int sum;
        public TreeNode convertBST(TreeNode root) {
            sum = 0;
            convertBST1(root);
            return root;
        }
    
        // 按右中左顺序遍历，累加即可
        public void convertBST1(TreeNode root) {
            if (root == null) {
                return;
            }
            convertBST1(root.right);
            sum += root.val;
            root.val = sum;
            convertBST1(root.left);
        }
    }

class Solution {
        //DFS iteraion統一迭代法
        public TreeNode convertBST(TreeNode root) {
            int pre = 0;
            Stack<TreeNode> stack = new Stack<>();
            if(root == null) //edge case check
                return null;
    
            stack.add(root);
    
            while(!stack.isEmpty()){
                TreeNode curr = stack.peek();
                //curr != null的狀況，只負責存node到stack中
                if(curr != null){ 
                    stack.pop();
                    if(curr.left != null)       //左
                        stack.add(curr.left);
                    stack.add(curr);            //中
                    stack.add(null);
                    if(curr.right != null)      //右
                        stack.add(curr.right);
                }else{
                //curr == null的狀況，只負責做單層邏輯
                    stack.pop();
                    TreeNode temp = stack.pop();
                    temp.val += pre;
                    pre = temp.val;
                }
            }
            return root;
        }
    }

### 总结：（待补充） ###

[LeetCode_ -]: https://leetcode.cn/problems/trim-a-binary-search-tree/
[Link 1]: https://www.programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[083a1e889ef9adb6bf908d217a29ca9f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/6c9b3c22528a4c3c9989b88773c1cf9f.png
[a995d38083247583827ea073a586d2fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/06e8657ff7254cdfb9b59546a6674248.png
[LeetCode_669. _bilibili]: https://www.bilibili.com/video/BV17P41177ud?share_source=copy_web
[LeetCode_ - 1]: https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
[Link 2]: https://www.programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[944edc2fb3cf82bd5f980fee43b2cce9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/92f3955bb14d46e19787d75c64641507.png
[LeetCode_108._bilibili]: https://www.bilibili.com/video/BV1uR4y1X7qL?share_source=copy_web
[LeetCode_ - 2]: https://leetcode.cn/problems/convert-bst-to-greater-tree/
[Link 3]: https://www.programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[ab734b4161d2dd6e091702ccea418175.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d7ef8afaa09b47bfa9d8703979c3a335.png
[LeetCode_538._bilibili]: https://www.bilibili.com/video/BV1d44y1f7wP?share_source=copy_web