LeetCode 222. Count Complete Tree Nodes

[Woodyiiiiiii]

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

---

这道题求的是完全二叉树的节点数。

最简单的方法是直接用先序遍历，遍历所有的节点，这样的时间复杂度是O(n)(n是节点个数)，但甚至可以用一行代码来解决：

class Solution {
    int num = 0;
    public int countNodes(TreeNode root) {
        preOrder(root);
        return num;
    }
    void preOrder(TreeNode node) {
        if (node == null) return;
        ++num;
        preOrder(node.left);
        preOrder(node.right);
    }
}

显然上述方法没有利用到完全二叉树的特性，其不可能出现一个只有右孩子而没有左孩子的节点。完全二叉树可以看成是一部分满二叉树加上最后一层叶子节点构成。所以我们可以分两部分求解。先求得二叉树的层数，然后求得满二叉树的节点数是2的层数幂次方减去一(int)Math.pow(2, layerNum - 1) - 1；接着去求最后一层节点数，每层递归，如果当前层数不是最后一层，返回0，否则返回1，最后回溯的结果就是最后一层节点数。这个方法时间复杂度大概是O(l + m)，l是树的深度，m是最后一层节点数。

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int layerNum = 0;
        TreeNode r = root;
        while (r != null) {
            r = r.left;
            layerNum++;
        }
        if (layerNum == 1) return 1;
        int sum = (int)Math.pow(2, layerNum - 1) - 1;
        sum += getLastLayerNum(root.left, layerNum, 2)
                + getLastLayerNum(root.right, layerNum, 2);
        return sum;
    }
    public int getLastLayerNum(TreeNode root, int layerNum, int nowLayer) {
        if (root == null) {
            return 0;
        }
        if (nowLayer == layerNum) {
            return 1;
        }
        return getLastLayerNum(root.left, layerNum, nowLayer + 1) + 
                getLastLayerNum(root.right, layerNum, nowLayer + 1);
    }
}

还有一种方法同样递归求解，同样每层递归，如果当前层是满二叉树，调用_(1 << height) - 1_，否则继续往下一层。

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        TreeNode left = root;
        TreeNode right = root;
        int height = 0;
        
        while(right != null) {
            left = left.left;
            right = right.right;
            height++;
        }
        if(left == null) { // Left subtree and right subtree is balanced
            return (1 << height) - 1;  // 2 ^ (height) - 1;
        } else { // Left subtree is deeper than right subtree
            return 1 + countNodes(root.left) + countNodes(root.right);
        }
    }
}

---

参考资料：

• https://leetcode.com/problems/count-complete-tree-nodes/
• https://leetcode.com/problems/count-complete-tree-nodes/discuss/712806/java-0ms
• [LeetCode] 222. Count Complete Tree Nodes grandyang/leetcode#222