222. 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.

Example:

1
2
3
4
5
6
7
8
Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

完全二叉树的定义：它是一棵空树或者它的叶子节点只出现在最后两层。若最后一层不满，则叶子节点只出现在最左侧。

对于满二叉树，如果层数为h，则总节点个数为：2h-1。
因此，对根节点的左右子树的高度进行统计，假设左子树的高度记做lh，右子树的高度记做rh。
1.如果lh == rh，说明左子树和右子树一样高，那么左子树一定是满二叉树，所以左子树的总结点个数为2lh-1-1。加上根节点，共有2lh-1个节点。然后再对右子树进行递归统计。
2.如果lh>rh，说明最后一层不满，但是倒数第二层必然是满的，因此右子树节点总数为2rh-1，再加上根节点，共有2rh-1个节点。再对左子树进行递归统计。