二叉搜索树 - LeetCode 700.二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。如果节点不存在，则返回 null 。

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null) {
            return root;
        }
        while(root != null) {
            if(root.val == val) {
                return root;
            }
            if(root.val < val){ 
                root = root.right;
            } else {
                root = root.left;
            }
        }
        return null;
    }
}

• 时间复杂度：O(N)，其中 N 是二叉搜索树的节点数。最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下我们需要迭代 N 次。
• 空间复杂度：O(1)，没有使用额外的空间。