求完全二叉树其节点的个数

public int countNodes(TreeNode root) {
        if (root == null) return 0;
        return bs(root,1,heightOfCompleteTree(root,1));
    }

    public static int heightOfCompleteTree(TreeNode root,int level){
        while (root != null){
            root = root.left;
            level++;
        }
        return level-1;
    }

    public static int bs(TreeNode root,int level, int height){
        if (level == height ) return 1;
        if (heightOfCompleteTree(root.right,level+1) == height){
            return (1<<(height - level)) + bs(root.right,level+1,height);
        }else {
            return (1<<(height - level - 1)) + bs(root.left,level+1,height);
        }
    }

System.out.println( 1 << 2+2 );   输出结果为16
>> 与 << 的运算优先级比 + - 要低

public static int heightOfCompleteTree(TreeNode root,int level){
        while (root != null){
            root = root.left;
            level++;
        }
        return level-1;
    }
    
这个函数的意思是：以level层的节点root计算这个树的最大的深度。