[!info] related notes 算法面试题型 MOC 二叉树高频题

Count Complete Tree Nodes

LeetCode: https://leetcode.cn/problems/count-complete-tree-nodes/

本题保证输入为完全二叉树；下面算法利用该前提，不负责判定完整性。任意树应改为普通遍历计数，或先用 完整性判定验证；后者会增加 O(n) 成本。

思路

完全二叉树的性质：

• 如果某子树是“满二叉树”（perfect tree），节点数可以直接用 2^h - 1 得到。
• 对当前节点 cur：比较 cur.right 的最左路径高度是否能到达整棵树的高度。
  • 如果能到达：说明左子树是满的，直接加上左子树节点数，再递归右子树。
  • 否则：说明右子树是满的，直接加上右子树节点数，再递归左子树。

这里 perfect 指每层都填满，而不是仅要求每个节点有 0 或 2 个孩子的 full/proper tree。h 与 level 按节点层数计，根位于第 1 层。

每层只递归一个非满子树，同时沿最左路径测高，因此时间 O((log n)^2)，递归栈 O(log n)。这依赖完全二叉树的高度与节点数关系。

Java Template

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int h = mostLeftLevel(root, 1);
        return count(root, 1, h);
    }

    // cur: current node
    // level: cur is at this level
    // h: total height of the tree
    private int count(TreeNode cur, int level, int h) {
        if (level == h) return 1;

        // if right subtree's leftmost level reaches height h,
        // left subtree is perfect
        if (mostLeftLevel(cur.right, level + 1) == h) {
            // left perfect nodes: 2^(h-level) - 1, plus current node => 2^(h-level)
            return (1 << (h - level)) + count(cur.right, level + 1, h);
        } else {
            // right perfect nodes: 2^(h-level-1) - 1, plus current node => 2^(h-level-1)
            return (1 << (h - level - 1)) + count(cur.left, level + 1, h);
        }
    }

    // returns the deepest level reachable by going left from cur
    private int mostLeftLevel(TreeNode cur, int level) {
        while (cur != null) {
            level++;
            cur = cur.left;
        }
        return level - 1;
    }
}

TreeNode 由题目环境提供。位移 1 << k 使用 Java 32 位 int；在本题节点数上限 50000 下安全，但不是任意高度都可用的幂运算。更大范围要同时检查移位、加法和返回类型，不能只把某个局部变量改成 long。

Related

• 二叉树高频题