Count Complete Tree Nodes
Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Analysis
Note:
- 1<<n == 2^n
- 一个complete tree的nodes数为2^height-1
- 假设root的height为h,那左边height数一定是h-1
- 如果左右height数相同为h-1
- 左边一定是complete tree
- nodes数为以下相加
- root:1
- left sub tree: 2^(h-1) - 1
- right sub tree: nodes(right sub tree)
- 如果左右height数不同,右边height数一定是h-2
- 右边一定是height为h-2的complete tree
- nodes数为以下相加
- root: 1
- left sub tree: nodes(left sub tree)
- right sub tree: 2^(h-2) -1
Code
public class Solution {
public int countNodes(TreeNode root) {
int h = height(root);
if (h==0) {return 0;}
//如果左右subtree height想同,说明左subtree一定是complete tree,那么只要把
return height(root.right) == h-1 ? (1<<h-1) + countNodes(root.right) : (1<<h-2) + countNodes(root.left);
}
//helper funciton to count the height of a tree
private int height(TreeNode root){
return root==null? 0 : 1+height(root.left);
}
}