算法23|669，108，538

669. 修剪二叉搜索树

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        #终止条件
        if root is None:
            return None
        #判断root的值大于最高值,寻找符合条件的节点,不可以返回root.left,因为直接断掉后面符合条件的数值
        if root.val > high:
            left = self.trimBST(root.left,low,high)
            return left
        #判断root的值小于最高值,寻找符合条件的节点
        if root.val < low:
            right = self.trimBST(root.right,low,high)
            return right
        root.left = self.trimBST(root.left,low,high)
        root.right = self.trimBST(root.right,low,high)
        return root

题目链接/文章讲解： 代码随想录

视频讲解： 你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树_哔哩哔哩_bilibili

二刷（未ac）

var trimBST = function(root, low, high) {
    if(root === null){
        return null;
    }
    if(root.val < low){
        let right = trimBST(root.right,low,high);
        return right;
    }
    if(root.val > high){
        let left = trimBST(root.left,low,high);
        return left;
    }
    root.left =trimBST(root.left,low,high);
    root.right = trimBST(root.right,low,high);
    return root;
};
 

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

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def traversal(nums,left,right):
            if left >right:return None
            mid = left+(right-left)//2
            root = TreeNode(nums[mid])
            root.left = traversal(nums,left,mid-1)
            root.right = traversal(nums,mid+1,right)
            return root
        return traversal(nums,0,len(nums)-1)

因为需要构造平衡二叉树，所以得分为左区间、右区间和中间节点

代码随想录

视频讲解：构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树_哔哩哔哩_bilibili

二刷：这道题比较简单，但是我还是没有ac

var sortedArrayToBST = function (nums) {
    // 找中间
    // 分两两边
    const find = 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 = find(nums,left,mid-1)
        root.right = find(nums,mid+1,right)
        return root
    }
    return find(nums,0,nums.length-1)
};

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

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        pre = 0
        def traversal(cur):
            nonlocal pre
            #终止条件
            if cur is None:
                return 
            #右
            traversal(cur.right)
            #中
            cur.val += pre
            #注意，这里是数值的变化
            pre = cur.val
            #左
            traversal(cur.left)
        traversal(root)     
        return root

使用双指针的方法，然后从右往左遍历，直到cur为空，再返回相加值

代码随想录

视频讲解：普大喜奔！二叉树章节已全部更完啦！| LeetCode：538.把二叉搜索树转换为累加树_哔哩哔哩_bilibili

二刷：未ac

递归法和迭代法

var convertBST = function(root) {
    // 计算顺序右边中间左边
    let pre = null
    let cur = root
    const traversal = function(cur){
        if(cur === null){return }
        traversal(cur.right)
        if(pre !== null){
            cur.val += pre.val
        }
        pre = cur
        traversal(cur.left)
    }
    traversal(root)
    return root
};

var convertBST = function(root) {
    let stack = [];
    let pre = 0
    let cur = root
    while(cur !== null || stack.length > 0){
        if(cur !== null){
            stack.push(cur)
            cur = cur.right
        }else{
            cur = stack.pop()
            cur.val += pre  
            pre = cur.val
            cur = cur.left 
        }
    }
    return root;
};

总结篇

代码随想录