代码随想录算法训练营第十九天 | leetcode：修剪二叉搜索树 ,有序数组转换为二叉搜索树,二叉搜索树转换为累加树

_zzh 的个人博客 / 15 / 0 / 创建于 4个月前 / 更新于 4个月前

669. 修剪二叉搜索树

解题方法

修剪二叉搜索数有个坑，就是需要注意不能一刀切。当遍历到节点值小于low时不能直接返回，还需要检查当前节点右子树上是否存在大于等于low的节点。相对的high也是一样，当遍历到节点大于high时，也需要检查其左子树是否存在小于等与high的节点。
二叉搜索树使用中序遍历，保持遍历节点有序。修剪后节点衔接情况如下：

code

class Solution {

    /**
     * @param TreeNode $root
     * @param Integer $low
     * @param Integer $high
     * @return TreeNode
     */
    function trimBST($root, $low, $high) {
        if($root == null) return null;
        if($root->val < $low){
            //当前节点小于low,继续查找其右子树符合大于等low要求部分
            $right = $this->trimBST($root->right, $low, $high);
            return $right;
        }
        if($root->val > $high){
            //当前节点大于high,继续查找其左子树符合小于等于high要求部分
            $left = $this->trimBST($root->left, $low, $high);
            return $left;
        }

        //root->left接入符合条件的左孩子
        $root->left = $this->trimBST($root->left, $low, $high);
        //root->right接入符合条件的右孩子
        $root->right = $this->trimBST($root->right, $low, $high);
        return $root;
    }
}

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

需要注意的地方

回顾下平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
求中间值的越界问题：mid = left + (right - left)/2

解题方法

跟之前从中序与后序遍历序列构造二叉树的思路相同，先找中间值作为树的根节点，然后递归左右区间，构造左右子树即可。需要注意的是：当左/右区间为偶数时，取中间节点靠左还是靠右都行，对应的就是取中间值时是向上取整还是向下取整。最后的结果只是构造的二叉树不一样，如下图所示。而题目也提出答案不唯一。
本题区间采用左闭右闭区间，所以结束条件为left>right。因为[1,1]是合法区间。

code

class Solution {

    /**
     * @param Integer[] $nums
     * @return TreeNode
     */
    function sortedArrayToBST($nums) {
        $root = $this->traversal($nums, 0, count($nums) - 1);
        return $root;
    }

    function traversal($nums, $left, $right){
        if($left > $right) return null;
        //floor/ceil都可以  只是构建的二叉树不一样
        $mid = $left + floor(($right - $left)/2);
        $root = new TreeNode($nums[$mid]);
        $root->left = $this->traversal($nums, $left, $mid-1);
        $root->right = $this->traversal($nums, $mid+1, $right);
        //print_r($root);
        return $root;
    }
}

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

解题方法

请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。这句话一开始说实话每太看懂，直到看了讲解。
直白点说就是把当前节点的值，累加上比它更大的节点的值。例如下图黑色所标节点5：需要更新为5+6+7+8=26.
从图示看出应该从最大节点处开始遍历。所以转变下中序遍历为右中左。使用双指针，pre指针记录上一个节点的值，cur指针累计并修改当前节点值。

code

class Solution {
    private $pre = 0;
    /**
     * @param TreeNode $root
     * @return TreeNode
     */
    function convertBST($root) {
        if($root == null) return $root;
        //右
        $this->convertBST($root->right);
        //中
        //修改cur节点值
        $root->val += $this->pre;
        //更新pre指针
        $this->pre = $root->val;
        //左
        $this->convertBST($root->left);
        return $root;
    }
}