019. 二叉搜索树中的搜索_云泊683的博客-爱代码爱编程
题目链接:
大概思路:
二叉搜索树的特性:
如果子树不为空,则左子树所有节点的值均小于其根节点的值,而右子树均大于。
01.递归法(递归三部曲流程)
1.确定递归函数参数和返回类型:
参数传入一个搜索树的节点,以及要搜索的值。
TreeNode* searchBST(TreeNode* root, int val)
2.明确终止条件:
当递归遍历遇见空值的时候,以及遇见要搜索的值的时候,两者都返回“根节点”(这里的根节点是遍历到这位置的节点)
3.确定递归单层逻辑:
因为是二叉搜索树,为了利用他的特性,快速找到目标值,应判断“根节点”值与其左右子树的大小关系,小向左,大向右(”根节点“定义同 2 ),最后如果没有找到值,则返回空。
记得用一个临时变量接着递归得到的返回值。
TreeNode* result = NULL;
if (root->val > val) result = searchBST(root->left, val);
if (root->val < val) result = searchBST(root->right, val);
return result;
4.总代码:
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL || root->val == val) return root;
TreeNode* result = NULL;
if (root->val > val) result = searchBST(root->left, val);
if (root->val < val) result = searchBST(root->right, val);
return result;
}
};
02.迭代法:
由于搜索树的特性,所以没有像二叉树的迭代法那样需要回溯,可以很方便的去遍历可能性最大的路径(因为搜索树特性,这条路径要么有要么没有,其他路径一定没有)
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while (root != NULL) {
if (root->val > val) root = root->left;
else if (root->val < val) root = root->right;
else return root;
}
return NULL;
}
};