CBTNodeCount.java

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class CBTNodeCount {
    private int getHeight(TreeNode root) {
        if (root == null) { return 0; }
        return 1 + getHeight(root.left);
    }

    public int countNodes(TreeNode root) {
        if (root == null) { return 0; }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if (left == right) {
            return (int)Math.pow(2, left) + countNodes(root.right);
        } else {
            return (int)Math.pow(2, right) + countNodes(root.left);
        }
    }
}