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

计算一个完全二叉树的节点个数。其中完全二叉树是指除了最后一行，其余的每一行都必须是满节点的树。

思路一 ：不讲道理的递归

直接返回左子树和右子树的叶结点的个数。当然超时啦

1
2
3
4
public int countNodes(TreeNode root) {
    if(root==null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

思路二：讲道理的递归

思路一很明显没有充分利用这是一颗完全二叉树的条件。从另一个角度看，一颗完全二叉树的左子树和右子树有两种情况

  1. 左子树比右子树高
  2. 左子树和右子树一样高

当左子树和右子树一样高时，说明左子树本身是一颗满二叉树，它的元素个数为2^h左-1。
当左子树比右子树高时，说明右子树本身是一颗满二叉树，它的元素个数为2^h右-1(h为树的高度)

所以每一次通过判断左右子树的高度可以得到其中一棵子树的元素个数，这时再递归到另一颗子树继续计算直到当前元素为null。
代码如下：

1
2
3
4
5
6
7
8
9
int height(TreeNode root) {
    return root == null ? -1 : 1 + height(root.left);
}
public int countNodes2(TreeNode root) {
    int h = height(root);
    return h < 0 ? 0 :
           height(root.right) == h-1 ? (1 << h) + countNodes2(root.right)
                                     : (1 << h-1) + countNodes2(root.left);
}

思路三：递什么归！

当递归转化为循环且该循环并不需要使用栈这种数据结构时，性能往往会得到质的飞跃。在上面的思路二中采用递归，在这里我们将递归转变为循环。同时我们只需要计算一次树的高度，因为每一次选择的子树的高度都是上一个高度-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int height2(TreeNode root){
    if(root==null) return -1;
    int height = 0;
    while(root.left!=null) {height++; root=root.left;}
    return height;
}

public int countNodes3(TreeNode root) {
    int count = 0;
    int height = height2(root);
    while(root!=null){
        if(height2(root.right)==height-1){
            count += 1<<height;
            root = root.right;
        }else{
            count += 1<<height-1;
            root = root.left;
        }
        height--;
    }
    return count;
}