给出一个完全二叉树,求出该树的节点个数。
说明:
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
leetcode
解题思路:
- 如果是暴力做法,就只需要对树进行一次遍历就好,时间复杂度是O(N)的,但是这就没有利用到这里的要求,也就是完全二叉树。
- 根据完全二叉树的性质可知,总节点个数就是2的其层数次方 - 1。
- 这样,我们就可以递归各个层,每次获取完整的最底层的层数,判断左右树是不是完全二叉树,即可。
- 首先需要分别再当前层我们需要分别统计左右子树的最大深度,最大深度就是一直遍历左右子树的左节点。
- 如果左右子树的最大深度一样,那说明左树一定是完全二叉树,那么直接通过位移计算出左树的节点数,然后记得加上当前父节点,那就是2的层数次方大小。然后再去递归计算右树。
- 如果左右子树最大深度不一样,那说明右树一定是完全二叉树,然后计算右数,再递归左树。
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
int l = depth(root.left);
int r = depth(root.right);
if(l == r) {
// 左树是完全树,这里不用减一就是因为需要计算上当前节点
return countNodes(root.right) + (1 << l);
} else {
// 右树是完全二叉树
return countNodes(root.left) + (1 << r);
}
}
private int depth(TreeNode root) {
int deep = 0;
while(root != null) {
deep ++;
// 一直递归左树,才能直到完全二叉树的深度
root = root.left;
}
return deep;
}
}