669.修剪二叉搜索树

题目

【比增加和删除节点难的多】

给你二叉搜索树的根节点 root ，同时给定最小边界 low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在 [low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

示例 2：

输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]

提示：

• 树中节点数在范围 [1, 10<sup>4</sup>] 内
• 0 <= Node.val <= 10<sup>4</sup>
• 树中每个节点的值都是 唯一 的
• 题目数据保证输入是一棵有效的二叉搜索树
• 0 <= low <= high <= 10<sup>4</sup>

思路

• 将要删除的节点的右子树接到要删除节点的父节点上。
• 伪代码
  • 终止条件判断
    • null
    • 小于low
      • 向右继续遍历，返回right
    • 大于high
      • 向左继续遍历，返回left
  • 左右的递归
  • 返回root
• 代码

  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  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;  
      }
  }
  

总结

• 这道题代码一旦知道思路了就不难了。
• 误区，如果直接return right和return left，就忽略了删除节点的右子树下的左子树和删除节点的左子树下的右子树，因此需要在判断条件的时候再往一个方向遍历。

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

题目

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡 二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 10<sup>4</sup>
• -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
• nums 按 严格递增 顺序排列

思路

• 平衡二叉搜索树的定义

  • 任意节点的左子树和右子树的高度差(平衡因子)不超过1.平衡因子=|左子树高度-右子树高度|<=1

• 基础思路

  • 每次都以中间节点为分割点，递归。再以左子树的中间节点为分割点，以右子树的中间节点为分割点进行递归。
  • 中间节点是奇数，取这个值；是偶数的话都可以。

• 代码

  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  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;
  	}
  }
  
  

注意

• 终止条件是left>=right，如果设置为left>right会报错
• 区间的开闭影响代码的写法
  • if (left ? right) return null;
    • [left,right)，left>=right，当=时，区间为空
    • [left,right], left>right 需要明确调整右边界，当=时，有一个元素，因此不能加=
  • 递归时的区间
    • [ )
      • 左 [left.mid)，mid不属于左区间
      • 右[mid+1,right) 从mid+1开始
      • return sortedArrayToBST(nums,0,nums.length); //[)左闭右开
    • ( )
      • 左 [left.mid-1]，左区间是比mid小的元素
      • 右[mid+1,right] 从mid+1开始，右区间是比mid大的元素
      • TreeNode root = traversal(nums, 0, nums.length - 1);

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

题目

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

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

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

注意： 本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 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]

示例 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 和 10<sup>4</sup>^ ^之间。
• 每个节点的值介于 -10<sup>4</sup> 和 10<sup>4</sup> 之间。
• 树中的所有值 互不相同 。
• 给定的树为二叉搜索树。

思路

• 将前一个节点的值加到当前节点上。右中左，把比它大的值加进去
• 思路
  • 右中左倒中序遍历，加1
• 代码

  • /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    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);//左
        }
    }