700. 二叉搜索树中的搜索

题解：
思路一：

迭代：题目非常简单，普通的二叉搜索树查找。 代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

    // 二叉搜索树性质， 左子树的值都比根节点小， 右子树的值都比根节点大。
    // 当节点值小于 当前节点值时， 查找其左子树。
    // 当节点值大于 当前节点值时， 查找其右子树
    // 相等时 返回

    // 找到最后，不存在则返回 null
    // 迭代
    public TreeNode searchBST1(TreeNode root, int val) {

        while (root != null){
            if (root.val == val) return root;

            if (root.val > val){
                root = root.left;
            }else {
                root = root.right;
            }
        }
        return null;
    }

时间复杂度： O(H) ，其中H为树高，平均时间复杂度 O(log N), 最坏时间复杂度: O(N).

空间复杂度: O(1)。

思路二：

递归 ， 代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

    // 递归
    public TreeNode searchBST(TreeNode root, int val) {

        if (root == null) return root;

        if (root.val == val) return root;
        if (root.val > val) return searchBST(root.left,val);

        return searchBST(root.right,val);
    }

时间复杂度： O(H) ，其中H为树高，平均时间复杂度 O(log N), 最坏时间复杂度: O(N).

空间复杂度: O(H), 平均情况下深度为 O(log⁡N)，最坏情况下深度为 O(N)O(N)