给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
//找到第一个小于low的节点和大于high的节点 并且删除左边节点和其所有左子树 以及 右边节点和其所有右子树
if(root == nullptr) return root;
int num = root->val;
//找到第一个不在范围的元素
if(num >= low && num <= high){
if(root->left){
root->left = trimBST(root->left,low,high);
}
if(root->right){
root->right = trimBST(root->right,low,high);
}
}//不满足范围进行处理
else if(num < low){//删除该节点和其左子树
return trimBST(root->right,low,high);
}
else{
return trimBST(root->left,low,high);
}
return root;
}
};
标签:修剪,669,二叉,high,low,trimBST,root,节点
From: https://www.cnblogs.com/lihaoxiang/p/17308825.html