222. Count Complete Tree Nodes

二刷
先写了O(n)解法

100.00 %
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

一刷
Brute Force的方法是O(n)
可以根据性质进行优化
每一层O(logn) get height
总共logn层
Time O(logn^2)
           1
        /      \
     1         1
   /   \      /   \
 1    1    1    1


82.17 %


public class Solution {
    /* full tree : #nodex = 2^h - 1
    if (leftHeight == rightHeight) left is full
    if (leftHeight == rightHeight + 1) right is full
    */
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        //count of the root node
        int count = 1;
        //if (root.left == null && root.right == null) return count;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if (leftHeight == rightHeight) {
            //left is full
            count += (1 << leftHeight) - 1;
            count += countNodes(root.right);
        } else if (leftHeight == rightHeight + 1) {
            count += (1 << rightHeight) - 1;
            count += countNodes(root.left);
        } else {
            throw new RuntimeException("Invalid Complete Tree");
        }
        return count;
    }
    private int getHeight(TreeNode root) {
        int h = 0;
        while (root != null) {
            root = root.left;
            h++;
        }
        return h;
    }
}