修剪二叉树
给定一个二叉搜索树,同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点,所以结果应当返回修剪好的二叉搜索树的新的根节点。
示例 1:
输入:
1
/ \
0 2
L = 1
R = 2
输出:
1
\
2
示例 2:
输入:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
输出:
3
/
2
/
1
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/trim-a-binary-search-tree
解题思路
递归遍历二叉树,进行特殊情况的判断,如果 < $L,则只遍历他的右子树,如果 > $R,则只遍历左子树,其他在区间内的相当于重新赋值,无需额外处理。
php 代码
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @param Integer $L
* @param Integer $R
* @return TreeNode
*/
function trimBST($root, $L, $R) {
if ($root == null) {
return $root;
}
if ($root->val < $L) {
return $this->trimBST($root->right, $L, $R);
}
if ($root->val > $R) {
return $this->trimBST($root->left, $L, $R);
}
$root->left = $this->trimBST($root->left, $L, $R);
$root->right = $this->trimBST($root->right, $L, $R);
return $root;
}
}
最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券