算法

(暴力枚举) $O(log\,n)$

对于$bst$中的任意节点来说，它的左子树中的所有元素都比它小，右子树中的所有元素都比它大。然后利用这一特性去遍历$bst$。

时间复杂度

时间复杂度为$O(log\,n)$，其中$log\,n$为$bst$的高度。

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (root.val == val) return root;
            else if (root.val < val) root = root.right;
            else root = root.left;
        }
        return root;
    }
}