222. Count Complete Tree Nodes

class Solution {
    public int countNodes(TreeNode root) {
        // height: 1-based, h; number of nodes: N
        // N = 2^h-1;
        if(root==null) return 0;
        int leftHeight = getHeight(root);
        int rightHeight = getHeight(root.right)+1;

        return leftHeight == rightHeight ? (1 << rightHeight-1) + countNodes(root.right) : (1 << rightHeight-1)+countNodes(root.left);
    }
    
    private int getHeight(TreeNode root){
        if(root == null) return 0;
        return 1+getHeight(root.left);
    }
}