Thinking process

https://discuss.leetcode.com/topic/15533/concise-java-solutions-o-log-n-2

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

        int left = getLeftHeight(root.left);
        int right = getLeftHeight(root.right);

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

    private int getLeftHeight(TreeNode node) {
        int result = 0;
        while (node != null) {
            result++;
            node = node.left;
        }

        return result;
    }
}