222. 完全二叉树的节点个数 (opens new window)

1.完全二叉树中的子问题

核心思路是找到满二叉树，因为它的节点个数可以直接根据树高进行计算。对于一棵完全二叉树：

• 左子树的树高等于右子树的树高：说明左子树一定是一棵满二叉树。此时只需要遍历右子树
• 左子树不等于右子树的树高：右子树高肯定小于左子树书高。说明右子树一定是一棵满二叉树。此时只需要遍历左子树。

计算树高时，因为完全二叉树的结构，每次只需要遍历左孩子节点，存在则层数加一。

树高计算时间复杂度O(log2 n)，整个二叉树的总层数O(log2 n)，每一层都会有两个节点进行树高计算，因此总时间复杂度O(log2 n * log2 n)

class Solution {
    public int countNodes(TreeNode root) {
        int res=0;
        while(root!=null){
            int leftdep=getDepth(root.left);
            int rightdep=getDepth(root.right);
            if(leftdep==rightdep){
                res+=(1<<leftdep);
                root=root.right;
            }
            else{
                res+=(1<<rightdep);
                root=root.left;
            }
        }
        return res;
    }
    public int getDepth(TreeNode root){
        int  depth=0;
        while(root!=null){
            root=root.left;
            depth++;
        }
        return depth;
    }
}