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

最近开始刷力扣，将每日做题心得都会发布在这上面，以便日后查看。

起初看到这个题，忘记了完全二叉树的概念是什么，于是回顾一下。

这里参考了以下链接

满二叉树、完全二叉树、平衡二叉树、最优二叉树

时间复杂度：O(logn * logn)

空间复杂度：O(1)

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftDepth = getDepth(root.left);
        int rightDepth = getDepth(root.right);
        if(leftDepth == rightDepth){
            //左子树为满树，递归右子树
            return countNodes(root.right) + (1 << leftDepth);
        }else{
            //右子树为满树，递归左子树
            return countNodes(root.left) + (1 << rightDepth);
        }


    }

    //得到树的深度
    public int getDepth(TreeNode node){
        TreeNode root = node;
        int depth = 0;
        while(root != null){
            depth++;
            root = root.left;
        }
        return depth;
    }

}