代码随想录算法训练营第二十三天- 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树、总结篇

今日学习

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

https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV1uR4y1X7qL

第一想法

既然是平衡的，那么必然是找mid，用递归秒了，注意结束的位置，当left>right

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined 0 : val)
 *     this.left = (left===undefined null : left)
 *     this.right = (right===undefined null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
    const buildtree = function (nums, left, right) {
        if (left > right) return null
        let mid = Math.floor(left + (right - left) / 2)

        let root = new TreeNode(nums[mid])
        root.left = buildtree(nums, left, mid - 1)
        root.right = buildtree(nums, mid + 1, right)
        return root
    }
    return buildtree(nums, 0, nums.length - 1)
};

把二叉树转换为累加树

https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV1d44y1f7wP

第一想法

注意读题，要从最右侧开始向左加，运用递归，中序遍历改变当前节点的val，

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined 0 : val)
 *     this.left = (left===undefined null : left)
 *     this.right = (right===undefined null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function (root) {
    let pre = 0
    const leijia = function (cur) {
        if (cur) {
            leijia(cur.right)
            cur.val += pre
            pre = cur.val
            leijia(cur.left)
        }
        return cur
    }
    return leijia(root)
};