完全二叉树结点数

给定一棵完全二叉树的头节点head，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。 

 

 

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}*/
public class Solution {
    public int nodeNum(TreeNode head) {
    	if (head == null) {
    		return 0;
    	}
    	return solve(head, 1, mostLeftLevel(head, 1));
    }

	private int solve(TreeNode head, int i, int h) {
		if (i == h) {
			return 1;
		}
		if (mostLeftLevel(head.right, i+1) == h) {
			return solve(head.right, i+1, h) + (1 << (h-i));
		} else {
			return solve(head.left, i+1, h) + (1 << (h-i-1));
		}
	}

	private int mostLeftLevel(TreeNode head, int i) {
		while (head != null) {
			i++;
			head = head.left;
		}
		return i-1;
	}
}