代码随想录day20 | leetcode 669.修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树

修剪二叉搜索树

以下是修剪二叉搜索树的步骤：

1. 如果当前节点为空，直接返回空。
2. 如果当前节点的值小于L，那么它和它的左子树都不在范围内，应该修剪掉。因此，返回修剪其右子树的结果，右子树中可能含有符合条件的结果，对其修剪。
3. 如果当前节点的值大于R，那么它和它的右子树都不在范围内，应该修剪掉。因此，返回修剪其左子树的结果。
4. 如果当前节点的值在L和R之间，那么保留当前节点，并递归修剪其左右子树。

public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null){return null;}if (root.val<low){TreeNode node = trimBST(root.right,low,high);//修剪左孩子的右子树return node;}if (root.val>high){TreeNode node = trimBST(root.left,low,high);return node;}root.left = trimBST(root.left,low,high);root.right = trimBST(root.right,low,high);return root;}

---

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

题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
构造二叉树：为了保证平衡，使左区间的节点数与右区间的节点数相同，从中间选取根节点，切割数组使用左闭右闭，递归重复步骤。

 public TreeNode sortedArrayToBST(int[] nums) {TreeNode root = PF(nums,0,nums.length-1);return root;}public TreeNode PF(int[] nums,int left, int right){TreeNode root;if (left> right){//当left = right 时数组中只有一个元素，也需要做处理。return null;}int mid = (left + right)/2;root = new TreeNode(nums[mid]);root.left = PF(nums,left,mid-1);root.right = PF(nums,mid+1,right);return root;}

---

把二叉搜索树转换为累加树

中序遍历：从小到大。累加，从大到小。
从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了

int per = 0;//如果 per 是局部变量，那么它在每次调用时都会被重置，这样就无法实现累加的效果。public TreeNode convertBST(TreeNode root) {dft(root);return root;}public void dft(TreeNode root){if (root==null){return;}dft(root.right);per += root.val;root.val = per;dft(root.left);}