在二分搜索树里查找算法

发表于 更新于 分类于
学习笔记

算法

基础树节点

1
2
3
4
5
6
7
8
9
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

算法 1

1
2
3
4
5
6
7
8
9
public boolean search(TreeNode root, int element) {
    if (root == null)
        return false;
    if (root.val == element)
        return true;
    if (root.val > element)
        return search(root.left, element);
    return search(root.right, element);
}

算法 2

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean search(TreeNode root, int element) {
    if (root == null)
        return false;
    while (root != null) {
        if (root.val == element)//如果查找成功则进行返回该节点
            return true;
        if (root.val > element)//遍历右子树
            root = root.right;
        else
            root = root.left;
    }
    return false;
}

时间复杂度 O(log n)