鹤山做网站公司,seo sem 做网站,百度有哪些产品,江苏营销型网站公司LeetCode 700.二叉搜索树中的搜索
1、题目
题目链接#xff1a;700. 二叉搜索树中的搜索 给定二叉搜索树#xff08;BST#xff09;的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在#xff0c;则…LeetCode 700.二叉搜索树中的搜索
1、题目
题目链接700. 二叉搜索树中的搜索 给定二叉搜索树BST的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在则返回 null 。
示例 1:
输入root [4,2,7,1,3], val 2
输出[2,1,3]示例 2:
输入root [4,2,7,1,3], val 5
输出[]提示
树中节点数在 [1, 5000] 范围内1 Node.val 107root 是二叉搜索树1 val 107
2、递归
思路
二叉搜索树是一个有序树满足以下性质
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树
据此可以得到如下算法 若 root 为空则返回空节点 若 val root.val则返回 root 若 val root.val递归左子树 若 val root.val递归右子树。
确定递归函数的参数和返回值
递归函数的参数传入的就是根节点和要搜索的数值返回的就是以这个搜索数值所在的节点。 代码如下
TreeNode* searchBST(TreeNode* root, int val)确定终止条件
如果root为空或者找到这个数值了就返回root节点。
if (root nullptr || root-val val) {return root;
}确定单层递归的逻辑
看看二叉搜索树的单层递归逻辑有何不同。 因为二叉搜索树的节点是有序的所以可以有方向的去搜索。 如果root-val val搜索左子树如果root-val val就搜索右子树最后如果都没有搜索到就返回 nullptr。 代码如下
TreeNode* result nullptr;
if (root-val val) result searchBST(root-left, val);
if (root-val val) result searchBST(root-right, val);
return result;代码
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root nullptr || root-val val) {return root;}// 如果根节点的值大于目标值则在左子树中继续搜索if (root-val val) {return searchBST(root-left, val);} else {// 如果根节点的值小于目标值则在右子树中继续搜索return searchBST(root-right, val);}}
};复杂度分析
时间复杂度: O(n)空间复杂度: O(n)
3、迭代法
思路
我们将方法一的递归改成迭代写法 若 root 为空则跳出循环并返回空节点 若 valroot.val则返回 root 若 valroot.val将 root 置为 root.left 若 valroot.val将 root 置为 root.right。
代码
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while (root ! nullptr) {if (root-val val) {root root-left;} else if (root-val val) {root root-right;} else {return root;}}return nullptr;}
};复杂度分析
时间复杂度: O(n)空间复杂度: O(1)
