day19|669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。

示例 1

输入root = [1,0,2], low = 1, high = 2

输出[1,null,2] 

示例 2

输入root = [3,0,4,null,2,null,null,1], low = 1, high = 3

输出[3,2,null,1] 

问题分析

当遍历到节点不在范围内需删除。此时不能return null而是要继续遍历此节点的子树。例如

if (root.val<low)    return root.right;//错误写法

 当删除0后需要继续向右子树遍历不能直接return root.right因为可能会有比low小的节点1也直接返回给了7的左子树方向

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root==null) return null;
        if (root.val<low){
            TreeNode right=trimBST(root.right,low,high);//当此时的节点小于low就把右子树有可能小于low所以需要递归判断每个节点放到上一个节点
            return right;
        }
        if (root.val>high){
            TreeNode left=trimBST(root.left,low,high);//当此时的节点大于high就把左子树有可能大于high所以需要递归判断每个节点放到上一个节点
            return left;
        }

        root.left=trimBST(root.left,low,high);//接收下一层的节点
        root.right=trimBST(root.right,low,high);//接收下一层的节点
        return root;

    }
}

---

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

给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1

输入nums = [-10,-3,0,5,9]

输出[0,-3,9,-10,null,5]

解释[0,-10,5,null,-3,null,9] 也将被视为正确答案 

示例 2

输入nums = [1,3]

输出[3,1]

解释[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。 

问题分析

找中间节点然后分出左区间和右区间左闭右闭。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return traversal(nums,0, nums.length-1);//左闭右闭
    }
    public TreeNode traversal(int[] nums,int left,int right){
        if (left>right) return null;
        int mid=(left+right)/2;
        TreeNode node=new TreeNode(nums[mid]);
        node.left=traversal(nums,left,mid-1);
        node.right=traversal(nums,mid+1,right);
        return node;
    }
}

---

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

给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下二叉搜索树满足下列约束条件

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

示例 1

输入[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]

输出[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]   

示例 2

输入root = [0,null,1]

输出[1,null,1]   

示例 3

输入root = [1,0,2]

输出[3,3,2]

示例 4

输入root = [3,2,4,1]

输出[7,9,4,10]

问题分析

 二叉搜索树左中右为正序但是本题从倒序开始相加也就是从最大的数开始相加所以遍历顺序为右中左。定义双指针pre和curpre为int型若是TreeNode型会引起空指向用int会比较方便。

class Solution {
    int pre=0;//定义前一个节点的数值
    public TreeNode convertBST(TreeNode root) {
        traversal(root);
        return root;
    }
    public void traversal(TreeNode cur){//只是改树的节点的值无返回值
        if (cur==null) return;
        traversal(cur.right);//右

        if (pre!=0){//中
            cur.val=cur.val+pre;
        }
        pre=cur.val;

        traversal(cur.left);//左
    }
}