刷题笔记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);}
}