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

下一章开始刷图算法