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

669. 修剪二叉搜索树

解题方法

  1. 修剪二叉搜索数有个坑,就是需要注意不能一刀切。当遍历到节点值小于low时不能直接返回,还需要检查当前节点右子树上是否存在大于等于low的节点。相对的high也是一样,当遍历到节点大于high时,也需要检查其左子树是否存在小于等与high的节点。
    代码随想录算法训练营第十九天 | leetcode:修剪二叉搜索树 ,有序数组转换为二叉搜索树,二叉搜索树转换为累加树
  2. 二叉搜索树使用中序遍历,保持遍历节点有序。修剪后节点衔接情况如下:
    代码随想录算法训练营第十九天 | leetcode:修剪二叉搜索树 ,有序数组转换为二叉搜索树,二叉搜索树转换为累加树

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

解题方法

  1. 跟之前从中序与后序遍历序列构造二叉树的思路相同,先找中间值作为树的根节点,然后递归左右区间,构造左右子树即可。需要注意的是:当左/右区间为偶数时,取中间节点靠左还是靠右都行,对应的就是取中间值时是向上取整还是向下取整。最后的结果只是构造的二叉树不一样,如下图所示。而题目也提出答案不唯一。
    代码随想录算法训练营第十九天 | leetcode:修剪二叉搜索树 ,有序数组转换为二叉搜索树,二叉搜索树转换为累加树
  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. 把二叉搜索树转换为累加树

解题方法

  1. 请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。这句话一开始说实话每太看懂,直到看了讲解。
    直白点说就是把当前节点的值,累加上比它更大的节点的值。例如下图黑色所标节点5:需要更新为5+6+7+8=26.
    代码随想录算法训练营第十九天 | leetcode:修剪二叉搜索树 ,有序数组转换为二叉搜索树,二叉搜索树转换为累加树
  2. 从图示看出应该从最大节点处开始遍历。所以转变下中序遍历为右中左。使用双指针,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;
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!