快速求完全二叉树的节点个数

作者：Grey

原文地址：快速求完全二叉树的节点个数

题目链接#

LeetCode 222. 完全二叉树的节点个数

题目进阶要求

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

暴力解法#

不考虑完全二叉树的这个性质，直接遍历一下二叉树，收集一下左右子树的节点个数，然后加上头节点，就是整个完全二叉树的节点个数，完整代码如下

    public static int countNodes1(TreeNode head) {
        if (head == null) {
            return 0;
        }
        return p(head).all;
    }
    public static Info p(TreeNode head) {
        if (head == null) {
            return new Info(0);
        }
        Info leftInfo = p(head.left);
        Info rightInfo = p(head.right);
        // 收集左右子树节点个数加上头节点，就是整棵树的节点个数
        int all = leftInfo.all + rightInfo.all + 1;
        return new Info(all);
    }

    public static class Info {
        public int all;
        public Info(int a) {
            all = a;
        }
    }

时间复杂度是O(N)。

最优解#

需要利用一下完全二叉树的性质，首先，我们知道，树的高度，深度，层次有如下关系：

对于一棵完全二叉树，头节点一直往左滑直到叶子节点得到的层数一定是这个二叉树的最大层数，假设这个值为h。

如果这个二叉树右树的最左节点的层数正好等于h，说明这个二叉树左树一定是满二叉树

如果这个二叉树右树的最左节点的层数不等于h，则说明这个二叉树的右树一定是满二叉树

由于满二叉树的节点个数可以通过树的高度计算出来：

    public static int countNodes(TreeNode head) {
        if (head == null) {
            return 0;
        }
        int h = maxLenOfLeft(head, 1);
        return count(head, 1, h);
    }

    private static int count(TreeNode head, int level, int h) {
        if (level == h) {
            return 1;
        }
        if (maxLenOfLeft(head.right, level + 1) == h) {
            // 左树一定是满的
            return (1 << (h - level)) + count(head.right, level + 1, h);
        } else {
            // 右数一定是满的，注意高度是 h - level - 1
            return (1 << (h - level - 1)) + count(head.left, level + 1, h);
        }
    }

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

通过如上方法，我们无须遍历整个二叉树，就可以把节点计算出来，复杂度低于O(N)。

更多#

算法和数据结构笔记