太强了!这个算法让面试官当场惊呼-你是怎么想到的

在这里插入图片描述

如果是普通二叉树，我们只能老老实实遍历每个节点,时间复杂度为O(N)。

但完全二叉树有特殊的结构性质，利用完全二叉树的特性，我们可以将时间复杂度优化到O(logN × logN)。

如果左子树是满二叉树，由满二叉树的节点数公式2^h - 1(h为高度)，可以直接算出左子树节点数，之后只需递归右子树。

反之，如果右子树是满的，则左子树需要继续递归。

代码逻辑

1. 主函数入口

1
2
3
4
5
6


public static int countNodes(TreeNode head) {
    if (head == null) {
        return 0;
    }
    return f(head, 1, mostLeft(head, 1));
}

2. 计算树的高度

1
2
3
4
5
6
7


public static int mostLeft(TreeNode cur, int level) {
    while (cur != null) {
        level++;
        cur = cur.left;
    }
    return level - 1;
}

3. 递归函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


public static int f(TreeNode cur, int level, int h) {
    if (level == h) {
        return 1;
    }
    if (mostLeft(cur.right, level + 1) == h) {
        // 情况1:右子树的最左节点到达最深层
        return (1 << (h - level)) + f(cur.right, level + 1, h);
    } else {
        // 情况2:右子树的最左节点未到达最深层
        return (1 << (h - level - 1)) + f(cur.left, level + 1, h);
    }
}

完整代码

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


    public static int countNodes(TreeNode head) {
        if (head == null) {
            return 0;
        }
        return f(head, 1, mostLeft(head, 1));
    }

    public static int f(TreeNode cur, int level, int h) {
        if (level == h) {
            return 1;
        }
        if (mostLeft(cur.right, level + 1) == h) {
            return (1 << (h - level)) + f(cur.right, level + 1, h);
        } else {
            return (1 << (h - level - 1)) + f(cur.left, level + 1, h);
        }
    }

    public static int mostLeft(TreeNode cur, int level) {
        while (cur != null) {
            level++;
            cur = cur.left;
        }
        return level - 1;
    }

如果觉得有帮助，欢迎点赞、关注、转发~