No.1

题目

修剪二叉搜索树

思路

• 递归法
• 有点抽象，要对具体案例做模拟才好懂

递归分析

1. 返回值：节点，参数：节点，[下界，上界]
2. 终止条件：遇到空节点，返回空
3. 单层递归逻辑：判断不在范围内的情况：当前节点小于下界/大于上界，直接返回右/左子树递归结果；若在范围内，则递归筛查左右子树，返回当前节点

代码

public TreeNode trimBST(TreeNode root, int low, int high) {  
    if (root == null)  
        return null;  
  
    if (root.val < low)  
        return trimBST(root.right, low, high);  
    if (root.val > high)  
        return trimBST(root.left, low, high);  
    root.left = trimBST(root.left, low, high);  
    root.right = trimBST(root.right, low, high);  
  
    return root;  
}

No.2

题目

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

思路

• 有序数组转BST，还要求高度平衡
• 递归法，分割区间

递归分析

1. 返回值：节点，参数：数组，[下界，上界)
2. 终止条件：下界大于等于上界，返回空
3. 单层递归分析：以中点分割，递归左右子树

代码

public TreeNode helper(int[] nums, int left, int right) {  
    if (left >= right)  
        return null;  
  
    int midIndex = left + (right - left) / 2;  
    TreeNode node = new TreeNode(nums[midIndex]);  
    node.left = helper(nums, left, midIndex);  
    node.right = helper(nums, midIndex + 1, right);  
      
    return node;  
}  
  
public TreeNode sortedArrayToBST(int[] nums) {  
    return helper(nums, 0, nums.length);  
}

No.3

题目

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

思路

• 递归反中序遍历
• 全局变量pre

递归分析

1. 返回值：空，参数：子树的根
2. 终止条件：遇到空节点，返回；
3. 单层递归逻辑
   1. 递归右子树；
   2. 更新根节点累加值，记录到pre
   3. 递归左子树；

代码

private int preVal = 0;  
public void convertHelper(TreeNode node) {  
    if (node == null)  
        return;  
  
    convertHelper(node.right);  
    node.val += preVal;  
    preVal = node.val;  
    convertHelper(node.left);  
}  
  
public TreeNode convertBST(TreeNode root) {  
    convertHelper(root);  
    return root;  
}