代码随想录算法训练营第十七天｜LeetCode 108. 将有序数组转换为二叉搜索树、 538. 把二叉搜索树转换为累加树

二叉树的第八天！

题目链接：108. 将有序数组转换为二叉搜索树

状态：一次性AC

这题相对而言比较简单，只需注意好边界的处理就好。具体做法是先确定好开闭区间情况，我是左闭右闭，所以之后在处理边界情况时要注意我的右边区间的值是可以取到的。所以在我的递归方法的健壮性判断中就应该是if(left > right) return null; 此处不能写 >= 是因为 left = right 的情况是可以存在的 正常情况。完整代码如下：

class Solution { // Java
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = traversal(nums, 0, nums.length - 1);
        return root;
    }
    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;
    }
}

复杂度分析：
时间复杂度：O(n). 因为每个元素被处理一次
空间复杂度：O(log n). 最坏情况是O(h)，h为树高，但是因为是平衡二叉树，所以是log n.

题目链接：538. 把二叉搜索树转换为累加树

状态：一次性AC

这题也不太难，只需想清楚 右中左 的处理顺序就好，因为把顺序颠倒之后就可以轻松用双指针来实现逐步的累加了。所以递归的方法如下：1. 参数只需TreeNode root； 2. 终止条件是遍历到null； 3. 单层递归逻辑是右中左，其中 中 的部分就是累加。完整代码如下：

class Solution { // Java
    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);
    }
}

复杂度分析：
时间复杂度：O(n). 因为每个元素被处理一次
空间复杂度：O(h). h为树高