代码随想录训练营Day23:● 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树 ● 总结篇

669. 修剪二叉搜索树

题目链接

https://leetcode.cn/problems/trim-a-binary-search-tree/description/

题目描述

在这里插入图片描述

思路

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.left = trimBST(root.left,low,high);
        root.right = trimBST(root.right,low,high);
        return root;
    }

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

题目链接

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

题目描述

在这里插入图片描述

思路

public TreeNode sortedArrayToBST(int[] nums) {
        return get(nums,0,nums.length-1);
    }

    //定义一个方法去实现功能
    //取数组中间的数作为二叉搜索平衡树的根节点
    //然后将中间节点的左侧作为左子树，右侧作为右子树
    public TreeNode get(int[] nums,int left,int right){
        if(left>right) return null;
        int mid = (left+right)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = get(nums,0,mid-1);
        root.right = get(nums,mid+1,nums.length-1);
        return root;
    }

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

题目链接

https://leetcode.cn/problems/convert-bst-to-greater-tree/description/

题目描述

在这里插入图片描述

思路

pre 和 cur 双指针，不断向上移动进行累加

在这里插入图片描述

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