Day23:LeedCode 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树
669. 修剪二叉搜索树
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
示例 1：
输入：root = [1,0,2], low = 1, high = 2 输出：[1,null,2]
思路:
root.val<low:右子树可能存在满足要求的值,将修建后的右子树返回
root.val>high:左子树可能存在满足要求的值,将修剪后的左子树返回
low<=root.val<=high:左右子树都可能存在满足要求的值,修建左右子树,返回root
递归三部曲:
1.确定返回值和参数类型
因为是要遍历整棵树，做修改，其实不需要返回值也可以，我们也可以完成修剪（其实就是从二叉树中移除节点）的操作。
但是有返回值，更方便，可以通过递归函数的返回值来移除节点。
2.确定递归结束条件:
遇到空结点返回
3.确定单层递归逻辑:
root.val<low:右子树可能存在满足要求的值,将修建后的右子树返回
root.val>high:左子树可能存在满足要求的值,将修剪后的左子树返回
low<=root.val<=high:左右子树都可能存在满足要求的值,修建左右子树,返回root
代码参考:
class Solution {TreeNode trimBST(TreeNode root, int low, int high) {if(root==null)return null;if(root.val>high) return trimBST(root.left,low,high);if(root.val<low) return trimBST(root.right,low,high);root.left=trimBST(root.left,low,high);root.right=trimBST(root.right,low,high);return root;}
};108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
平衡
二叉搜索树。
示例 1：
输入：nums = [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
思路:将数组中间位置的数构建成新结点,将该数组一分为二构造左子树和右子树
代码参考:
class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums.length==0) return null;//寻找中间结点int mid=nums.length/2;//分割结点int[]left=Arrays.copyOfRange(nums,0,mid);int[]right=Arrays.copyOfRange(nums,mid+1,nums.length);TreeNode root=new TreeNode(nums[mid]);root.left= sortedArrayToBST(left);root.right=sortedArrayToBST(right);return root;}
}538. 把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
注意：本题和 1038: . - 力扣（LeetCode） 相同
示例 1：
输入：[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]
思路:中序遍历二叉搜索树能得到一串递增的数字,本题采用右中左遍历,用两个指针一个指向当前结点一个指向前一节点实现累计效果
递归三部曲:
1.返回值和参数类型
不需要递归函数的返回值做什么操作了，要遍历整棵树。
2.确定结束条件
遇空就终止。
3.单层递归逻辑
要右中左来遍历二叉树， 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。
代码参考:
class Solution {TreeNode pre=null;public void travel(TreeNode root){if(root==null) return ;travel(root.right);//不是第一个结点,当前结点值更新为前一结点加现在的结点值if(pre!=null)root.val=root.val+pre.val;pre=root;//更新上一结点travel(root.left);}public TreeNode convertBST(TreeNode root) {travel(root);return root;}
}