Count Complete Tree Nodes

题目

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

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 2hnodes inclusive at the last level h.

思路分析

看到这个题后会首先想到一个普通的binary tree如何count 所有的节点数，那就是用递归的方式，或者iterative的方式遍历所有的节点然后得到树上所有的节点数，这个很明显是O(n)的时间复杂度。

对于complete tree，求节点数有什么区别呢？能不能根据complete tree的特点来进行时间复杂度的优化呢？

首先可以用递归的方式来实现普通binary tree count节点数，O(n)的时间复杂度。

public int countNodes(TreeNode root) {
    if (root == null)
        return 0;
    return 1 + countNodes(root.left) + countNodes(root.right)

接下来考虑一下是不是有优化的方法

• 如果complete binary tree是一个full binary tree，那么可以根据数的height直接计算数的节点数
• 如果complete binary tree是一个full binary tree，那么root节点的左子树或者右子树必然至少有一是full binary tree

举例来说

    1
   / \
  2   3
 /
4

总的来说这个树不是full binary tree，但是root的右子树是full binary tree。

考虑到上面的两个重要的点，这道题可以做如下的优化，优化之后的时间复杂度变成什么了呢？O(log(n)^2)。为什么从O(n)大大简化成了O(log(n)^2)？那就是因为上面的第二点，每一次recursive的时候，两个call中至少有一个call会由于是full binary tree而停止。

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        int leftHeight = 0;
        int rightHeight = 0;
        TreeNode leftNode = root;
        TreeNode rightNode = root;
        while (leftNode != null){
            leftHeight ++;
            leftNode = leftNode.left;
        }
        while (rightNode != null){
            rightHeight ++;
            rightNode = rightNode.right;
        }
        if(leftHeight == rightHeight) return (1<<leftHeight)-1;
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}