刷题笔记24——完全二叉树的节点个数

有些事情是不能告诉别人的,有些事情是不必告诉别人的,有些事情是根本没有办法告诉别人的,而且有些事情是,即使告诉了别人,你也会马上后悔的。——罗曼罗兰

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

• java的幂运算要 (int) Math.pow(2,l+1)-1
• 计算满二叉树的节点数量公式：2 ^ height -1
• 一棵完全二叉树的两棵子树，至少有一棵是满二叉树
• 计算时间复杂度时，本题比较巧妙的就是，因为完全二叉树的子树也是完全二叉树，所以每次分叉只需要走其中一支即可,即O(logN)，而每次算深度即while循环这里需要O(logN)，因此时间复杂度为 O(logN*logN)
  

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null) return 0;
        int l = 0;
        int r = 0;
        TreeNode lt = root;
        while(lt.left!=null){
            lt = lt.left;
            l++;
        }
        TreeNode rt = root;
        while(rt.right!=null){
            rt = rt.right;
            r++;
        }

        if(l==r) return (int)Math.pow(2,l+1)-1;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

下一章开始刷图算法