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

题目链接：LeetCode222

题解

常规思路，遍历整棵树，时间复杂度O(N)，但是有一种时间复杂度小于O(N)的做法

首先遍历头结点右子树的最左边界，如果最左边界不为空，说明头结点的左子树是满二叉树，利用满二叉树的性质，结点个数就为$2^h-1$，再加上头结点，所以结果就是$2^h$，这个时间复杂度是O(logN)的，然后再递归遍历右子树求出有多少结点即可

如果最左边界为空，说明头结点的右子树是一棵高度为$h-1$的满二叉树，那么右子树加上头结点的总结点个数就为$2^{h-1}$，然后再递归遍历头节点的左子树即可

代码

class Solution {
    int h;
    public int countNodes(TreeNode root) {
        h = mostLeftLevel(root,1);
        if(root == null) 
            return 0;
        return bs(root,1);
    }
    public int bs(TreeNode node,int level) {
        if(level == h) 
            return 1;
        if(mostLeftLevel(node.right,level + 1) == h)
            return (1 << (h - level)) + bs(node.right,level + 1);
        return (1 << (h - level - 1)) + bs(node.left,level + 1);
    }
    public int mostLeftLevel(TreeNode node,int level) {
        while(node != null) {
            level++;
            node = node.left;
        }
        return level - 1;
    }
}