代码随想录-算法训练营day23【二叉树09：修剪二叉搜索树、将有序数组转换为二叉搜索树、把二叉搜索树转换为累加树】

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

第六章 二叉树part09
 今日内容：

● 669. 修剪二叉搜索树 
● 108.将有序数组转换为二叉搜索树 
● 538.把二叉搜索树转换为累加树 
● 总结篇 

 详细布置 

 669. 修剪二叉搜索树 

这道题目比较难，比 添加增加和删除节点难的多，建议先看视频理解。

题目链接/文章讲解： https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html  
视频讲解： https://www.bilibili.com/video/BV17P41177ud  

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

本题就简单一些，可以尝试先自己做做。

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  

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

本题也不难，在 求二叉搜索树的最小绝对差 和 众数 那两道题目 都讲过了 双指针法，思路是一样的。

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
 总结篇  

好了，二叉树大家就这样刷完了，做一个总结吧

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html   

往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL

0669_修剪二叉搜索树

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

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

总结篇

0669_修剪二叉搜索树

递归

701.二叉搜索树中的插入操作
450.删除二叉搜索树中的节点
669.修剪二叉搜索树

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;

public class _0669_修剪二叉搜索树 {
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution0669 {
    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在[low,high]范围内
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }

    //iteration，迭代法
    public TreeNode trimBST2(TreeNode root, int low, int high) {
        if (root == null)
            return null;
        while (root != null && (root.val < low || root.val > high)) {
            if (root.val < low)
                root = root.right;
            else
                root = root.left;
        }

        TreeNode curr = root;

        //deal with root's left sub-tree, and deal with the value smaller than low.
        while (curr != null) {
            while (curr.left != null && curr.left.val < low) {
                curr.left = curr.left.right;
            }
            curr = curr.left;
        }
        //go back to root;
        curr = root;

        //deal with root's righg sub-tree, and deal with the value bigger than high.
        while (curr != null) {
            while (curr.right != null && curr.right.val > high) {
                curr.right = curr.right.left;
            }
            curr = curr.right;
        }
        return root;
    }
}

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

做这道题目之前大家可以了解一下这几道：

106.从中序与后序遍历序列构造二叉树(opens new window)
654.最大二叉树 (opens new window)中其实已经讲过了，如果根据数组构造一棵二叉树。
701.二叉搜索树中的插入操作(opens new window)
450.删除二叉搜索树中的节点

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;

import java.util.LinkedList;
import java.util.Queue;

public class _0108_将有序数组转换为二叉搜索树 {
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution0108 {//递归：左闭右开，[left, right)
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length);
    }

    public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left >= right) {
            return null;
        }
        if (right - left == 1) {
            return new TreeNode(nums[left]);
        }
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, left, mid);
        root.right = sortedArrayToBST(nums, mid + 1, right);
        return root;
    }
}

class Solution0108_2 {//递归：左闭右闭，[left, right]
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = traversal(nums, 0, nums.length - 1);
        return root;
    }

    //左闭右闭区间[left, right]
    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;
    }
}

class Solution0108_3 {//迭代：左闭右闭，[left, right]
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;

        //根节点初始化
        TreeNode root = new TreeNode(-1);
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> leftQueue = new LinkedList<>();
        Queue<Integer> rightQueue = new LinkedList<>();

        // 根节点入队列
        nodeQueue.offer(root);
        // 0为左区间下标初始位置
        leftQueue.offer(0);
        // nums.size() - 1为右区间下标初始位置
        rightQueue.offer(nums.length - 1);

        while (!nodeQueue.isEmpty()) {
            TreeNode currNode = nodeQueue.poll();
            int left = leftQueue.poll();
            int right = rightQueue.poll();
            int mid = left + ((right - left) >> 1);

            // 将mid对应的元素给中间节点
            currNode.val = nums[mid];

            // 处理左区间
            if (left <= mid - 1) {
                currNode.left = new TreeNode(-1);
                nodeQueue.offer(currNode.left);
                leftQueue.offer(left);
                rightQueue.offer(mid - 1);
            }

            // 处理右区间
            if (right >= mid + 1) {
                currNode.right = new TreeNode(-1);
                nodeQueue.offer(currNode.right);
                leftQueue.offer(mid + 1);
                rightQueue.offer(right);
            }
        }
        return root;
    }
}

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

package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;

import java.util.Stack;

public class _0538_把二叉搜索树转换为累加树 {
}

class Solution0538 {
    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);
    }
}

class Solution0538_2 {
    //DFS iteraion统一迭代法
    public TreeNode convertBST(TreeNode root) {
        int pre = 0;
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) //edge case check
            return null;

        stack.add(root);

        while (!stack.isEmpty()) {
            TreeNode curr = stack.peek();
            //curr != null的状况，只负责存node到stack中
            if (curr != null) {
                stack.pop();
                if (curr.left != null)      //左
                    stack.add(curr.left);
                stack.add(curr);            //中
                stack.add(null);
                if (curr.right != null)     //右
                    stack.add(curr.right);
            } else {
                //curr == null的状况，只负责做单层逻辑
                stack.pop();
                TreeNode temp = stack.pop();
                temp.val += pre;
                pre = temp.val;
            }
        }
        return root;
    }
}