代码随想录算法训练营第十九天 | leetcode：修剪二叉搜索树 ,有序数组转换为二叉搜索树,二叉搜索树转换为累加树
0 / 0 / 创建于 11个月前 /
_zzh 的个人博客
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;
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号