222 Count Complete Tree Nodes

222. Count Complete Tree Nodes

1. Question

Given acompletebinary tree, count the number of nodes.

Definition of a complete binary tree fromWikipedia: 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.

2. Implementation

(1) Method 1

思路: 对于每个node，找出最左边和最右边的高度，如果这两个高度相同，说明这个树是完美二叉树，其node的数目等于 2^height - 1。如果这两个高度不同，递归地检测它的左子树和右子树是否完美二叉树，是的话就可以直接用公式计算, node数目等于它这个node加上左子树的node和右子树的node

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftMostHeight = getHeight(root, true);
        int rightMostHeight = getHeight(root, false);

        if (leftMostHeight == rightMostHeight) {
            return (1 << leftMostHeight) - 1;
        }

        return 1 + countNodes(root.left) + countNodes(root.right);
    }

    public int getHeight(TreeNode node, boolean isLeft) {
        int height = 0;

        while (node != null) {
            if (isLeft) {
                node = node.left;
            }
            else {
                node = node.right;
            }
            ++height;
        }
        return height;
    }
}

(2) Method 2 二分法

思路：根据Complete tree的leaf node as far left as possible的特点，对一个节点的左子树和右子树，我们分别找出最左的深度。如两边最左深度相同，说明左子树是完美二叉树，可以直接用公式计算node个数，否则右边子树的高度肯定小于左边子树，而且右边子树根据complete的特点也必然是完美二叉树，用公式计算其node个个数。这样就可以达到二分的效果

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int count = 1;

        int leftHeight = getLeftMostHeight(root.left);
        int rightHeight = getLeftMostHeight(root.right);

        if (leftHeight == rightHeight) {
            count += (1 << leftHeight) - 1;
            count += countNodes(root.right);
        }
        else {
            count += (1 << rightHeight) - 1;
            count += countNodes(root.left);
        }
        return count;
    }

    public int getLeftMostHeight(TreeNode node) {
        int height = 0;
        while (node != null) {
            node = node.left;
            ++height;
        }
        return height;
    }
}

3. Time & Space Complexity

Method 1: 时间复杂度 O(h^2), 解析: 最坏的情况是每个子树都不是完美二叉树，所以对于每个node，都要花2h的时间去找出它的左子树和右子树的高度，总的时间为 2h + 2(h-1) + 2(h-2) +. ... + 2 => O(h^2), 空间复杂度O(h)

Method 2: 时间复杂度: O(h^2), 空间复杂度O(h)

4. References

http://blog.csdn.net/jmspan/article/details/51056085