算法训练Day23|669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树

 1class Solution {
 2    public TreeNode trimBST(TreeNode root, int low, int high) {
 3        // 递归法遍历整棵树
 4        // 当节点值不介于low和high之间时，返回null
 5        if (root == null) return null;
 6        // 小于时向右遍历
 7        if (root.val < low) {
 8            return trimBST(root.right, low, high);
 9        } else if (root.val > high) { // 大于时，向左遍历
10            return trimBST(root.left, low, high);
11        } 
12        // 介于之间时，遍历该节点下的所有节点
13        root.left = trimBST(root.left, low, high);
14        root.right = trimBST(root.right, low, high);
15        return root;
16    }
17}

 1class Solution {
 2    public TreeNode sortedArrayToBST(int[] nums) {
 3
 4        // 调用辅助函数，传入数组和数组的边界索引
 5        return sortedArrayToBST(nums, 0, nums.length);
 6    }
 7
 8    public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
 9        // 如果左边界＞=右边界，表示没有元素，返回null
10        if (left >= right) {
11            return null;
12        }
13        // 如果只有一个元素，创建节点，将元素加入节点中，并返回节点
14        if (right - left == 1) {
15            return new TreeNode(nums[left]);
16        }
17        // 如果有多个元素，中间向两侧遍历、创建节点、赋值
18        int mid = left + (right - left) / 2;
19        TreeNode root = new TreeNode(nums[mid]);
20        // 构建该节点的左子树
21        root.left = sortedArrayToBST(nums, left, mid);
22        // 构建该节点的右子树
23        root.right = sortedArrayToBST(nums, mid + 1, right);
24        return root;
25    }
26}

 1class Solution {
 2    int sum; // 声明全局变量
 3    public TreeNode convertBST(TreeNode root) {
 4        convertBST1(root);
 5        return root;
 6    }
 7    // 单层递归逻辑
 8    public void convertBST1(TreeNode root) {
 9        // 终止条件
10        if (root == null) {
11            return;
12        }
13        convertBST1(root.right);
14        sum += root.val;
15        root.val = sum;
16        convertBST1(root.left);
17    }
18}