最近开始刷力扣,将每日做题心得都会发布在这上面,以便日后查看。
起初看到这个题,忘记了完全二叉树的概念是什么,于是回顾一下。
这里参考了以下链接
时间复杂度: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;
}
}