026.修剪二叉搜索树_云泊683的博客-爱代码爱编程
题目链接:
大概思路:
题目要求:
给一颗二叉搜索树和一个区间 [low,hight ],要求修剪二叉搜索树,把里面超过区间边界的值都去除掉,然后返回它。
思路:
递归遍历遇见不在区间的节点值,先判断再修剪。因为搜索树规律,小于区间,去右子树修剪,大于区间去左子树修剪,修剪完返回左或右子树给节点值的上层(这里有父节点接着,可以跳过需要删除的节点),完成删除操作。 最后遍历修剪完,返回root就可以了。
大概过程就是,不断递归遍历,遇见不在区间的节点值,把该区间可能需要修剪的左或右子树修剪了,然后跳过需要删除的节点值,它的左或右子树直接连接节点它的上一层节点。遇见非区间的值就修剪其左右子树,然后向上返回,直到遍历结束,搜索树就修剪完了。
递归三部曲:
1.确定递归函数参数和返回类型:
TreeNode* trimBST(TreeNode* root, int low, int high)
2.明确终止条件:
遍历遇见空返回。
if (root == nullptr ) return nullptr;
3.确定递归单层逻辑:
遇见不在区间的值就修剪它的左或右子树,依照大于hight还是小于low来定,小于low,修右子树,大于hight修左子树
if (root->val < low) {
TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
return right;
}
if (root->val > high) {
TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
return left;
}
然后正常递归(记得接住值) ,然后结束返回根节点就完成了。
root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;
4.总代码:
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr ) return nullptr;
if (root->val < low) {
TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
return right;
}
if (root->val > high) {
TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
return left;
}
root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;
}
};
个人想法:
一开始没想清楚其操作的过程是怎么发生的,描述的还是很模糊,描述清楚还是很难的,要不要试着全部描述清楚再下一题呢,我觉得可能费点时间,但是这样掌握的更牢固。可以试试。