Description
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.
Solution
Recursive
注意一定要仔细理解complete tree。对于每层来说，要么是满的，要么是连续的。
从root开始，分别沿着最左边和最右边计算高度，如果高度相同，则证明树是完全填满的，node数量直接根据height计算出；若高度不同，则递归调用。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root, true);
if (height(root, false) == leftHeight) {
// must use bit manipulation, otherwise it will TLE
return (1 << leftHeight) - 1;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
public int height(TreeNode root, boolean isLeft) {
int height = 0;
while (root != null) {
++height;
root = isLeft ? root.left : root.right;
}
return height;
}
}
