669.修剪二叉搜索树
题目链接：力扣
思路
上一道题目 450、删除二叉搜索树中的一个节点 是在二叉树中删除一个节点，只要找到被要被删除的节点之后进行删除返回就可以了，删除分几种情况
但是这道题目要删除的可能是多个节点，如果直接返回，那返回的子树里面还不知道是否还有要求删除的节点，所以返回的应该是被删除过的子树，这是这道题目区别于 删除一个节点 的根本区别
想明白了之后从在思路上比删除一个节点节点，只不过删除二叉搜索树一个节点的时候，有几种删除情况，删除节点左右都不为空的要保留左子树和右子树；而在区间删除中会直接删掉左子树或者右子树
修剪二叉搜索树
代码比较简单，但是想清楚这个逻辑比较复杂
如果节点小于low了，那么节点的左子树都不能要了，直接返回删除干净的右子树就可以
如果节点大于high了，那么节点的右子树都不能要了，直接返回删除干净的左子树就可以
代码不难，难的是想明白这个逻辑
想不清楚的时候画图最方便
class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null) { return null; } if (root.val < low) { TreeNode right = trimBST(root.right,low,high); return right; } if (root.val > high) { TreeNode left = trimBST(root.left,low,high); return left; } root.left = trimBST(root.left,low,high); root.right = trimBST(root.right,low,high); return root; } }
108.将有序数组转换成二叉树搜索树
题目链接：力扣
思路
一开始想复杂了，怎么都写不出来，现在就是一看就会，一写就废
为了保证是平衡二叉树，采用中间二分，一层一层递归
整体的思路就是，选取中间节点，构造左子树，构造右子树
题目也不要很难，为什么就是写不出来呢
将有序数组转换成二叉树搜索树
class Solution { public TreeNode sortedArrayToBST(int[] nums) { return sortNode(nums,0,nums.length-1); } TreeNode sortNode (int[] nums,int begin,int end) { if (begin > end) { return null; } // 单层递归的逻辑 int mid = (begin + end) / 2; TreeNode node = new TreeNode(nums[mid]); node.left = sortNode(nums,begin,mid-1); node.right = sortNode(nums,mid+1,end); return node; } }
538.把二叉树搜索树转换成累加树
题目链接：力扣
思路
这道题目真的很难读懂，就是说将每个节点中的值 改变成 原树中与该节点相等或比该节点值大的 所有节点的和。听起来多少是有点难受
二叉搜索树按照中序遍历其实是有序数组，那怎么求一个有序数组的累加和数组呢
定义两个指针，从数组后面开始遍历，将cur指向的位置和pre指向的位置的数字相加，赋值给cur，然后两个值依次往前推进，就可以得到累加和
这种方式也是可以用于二叉搜索树的，那我们就应该对二叉搜索树使用有序遍历，既然 左中右 是从小到大的有序数组，那么 右中左 就是对二叉搜索树的倒序遍历
处理逻辑上直接使用pre指针来保存不断累加的值就可以
把二叉树转换成累加树
class Solution { int pre = 0; public TreeNode convertBST(TreeNode root) { if (root == null) { return root; } // 右 convertBST(root.right); // 中 root.val += pre; pre = root.val; // 左 convertBST(root.left); return root; } }
