题解 | 二叉搜索树中的搜索

题干解析

题设给予我们一个二叉树和需要查找的节点值，要求我们查找到相应的节点并直接返回找到的节点。

算法思路

直接依照二叉搜索树的定义模拟查找即可。

实现代码

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        auto cur = root;
        while (cur && cur->val != val) {
            if (cur->val > val) cur = cur->left;
            else cur = cur->right;
        }
        return cur;
    }
};

复杂度分析

• 时间复杂度：最坏情况下，二叉树退化为链表，时间复杂度为
• 空间复杂度：只使用常数的额外空间，空间复杂度为