【代码随想录训练营】【Day23】第六章｜二叉树｜669. 修剪二叉搜索树 ｜108.将有序数组转换为二叉搜索树｜538.把二叉搜索树转换为累加树

修剪二叉搜索树

题目详细：LeetCode.669

做这道题之前建议先看视频讲解，没有想象中那么复杂：代码随想录—修剪二叉搜索树

由题可知，需要删除节点值不在区间内的节点，所以可以得到三种情况：

• 情况一：root.val < low
• 情况二：root.val > high
• 情况三：low < root.val < high
• 当节点满足情况一和情况二的条件时，删除该节点

但被删除节点的子树可能存在值在区间内的节点，利用二叉搜索树的特点可得：

• 情况一：root.val < low，root左子树上的节点值都比root.val小，右子树上的节点值都比root.val大，所以满足区间的节点只会在右子树上出现，递归修剪其右子树并返回新的子节点
• 情况二：root.val > high，root左子树上的节点值都比root.val小，右子树上的节点值都比root.val大，所以满足区间的节点只会在左子树上出现，递归修剪其左子树并返回新的子节点
• 情况三：low < root.val < high，说明当前节点不需要被删除，递归修剪其左右子树，返回修剪好的二叉搜索树的新的根节点

Java解法（递归）：

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(null == root) return null;// 根据二叉搜索树的特点可知if(root.val < low){// 删除节点的右子树中可能存在值在区间内的节点// 返回修剪好的右子树的新的子节点return trimBST(root.right, low, high);}else if(root.val > high){// 删除节点的左子树中可能存在值在区间内的节点// 返回修剪好的左子树的新的子节点return trimBST(root.left, low, high);}// else if(root.val > low && root.val < high)// 递归修剪左右子树root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);// 返回修剪好的二叉搜索树的新的根节点return root;}
}

---

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

题目详细：LeetCode.108

由题可知：

• 数组中的元素是有序排序的
• 转换的结果是为一棵高度平衡的二叉搜索树

要想使结果的二叉树高度平衡：

• 我们可以找中间值，根据中间值的下标将数组分为长度相近的两个子数组
• 利用数组有序的特点，其划分后的子数组依旧是有序的
  • 左边的数值较小 < 中间值，右边的数值 > 中间值
• 所以我们可以将中间值作为根节点，左边的数值作为左子树的节点，右边的数值作为右子树的节点
• 采用递归，按照以上的逻辑不断划分数组和子树，当nums无法再分时，将空节点或节点返回给上一层接收，决定了节点的位置
• 最后返回转换完成的二叉搜索树的根节点

Java解法（递归）：

class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums.length == 0) return null;else if(nums.length == 1) return new TreeNode(nums[0]);// 计算中间值的位置，并划分构建左右子树的子数组int mid = nums.length / 2;int[] left_nums = Arrays.copyOfRange(nums, 0, mid);int[] right_nums = Arrays.copyOfRange(nums, mid+1, nums.length);// 最中间的数值作为树的根节点，递归构建左右子树TreeNode root = new TreeNode(nums[mid]);root.left = sortedArrayToBST(left_nums);root.right = sortedArrayToBST(right_nums);// 返回构建完成的二叉搜索树的根节点return root;}
}

---

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

题目详细：LeetCode.538

做这道题之前建议先看视频讲解，没有想象中那么复杂：代码随想录—把二叉搜索树转换为累加树

Java解法（递归，双指针法）：

class Solution {int pre = 0;public TreeNode convertBST(TreeNode root) {this.inorder(root);return root;}public void inorder(TreeNode cur){if(null == cur) return;inorder(cur.right);cur.val += this.pre;this.pre = cur.val;inorder(cur.left);}
}

---