222. 完全二叉树的节点个数

class Solution {
    //如何比O(n)更快？不是剪枝，而是二分
    //剪枝只能带来小幅度的优化，不能改变最坏时间复杂度
    //为了跳出遍历所有节点的限制，我们转而计算高度：因为计算满二叉树的高度是logn的操作。
    //位运算的优先级很低
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int ans = 1;
        int l = calHeight(root.left);
        int r = calHeight(root.right);
        if (l == r) {
            ans += (1 << l) - 1;
            ans += countNodes(root.right);
        } else {
            ans += (1 << r) - 1;
            ans += countNodes(root.left);
        }
        return ans;
    }

    public int calHeight(TreeNode node) {
        if (node == null) return 0;
        return calHeight(node.left) + 1;
    }
}