求完全二叉树的节点个数

发表于 阅读次数：

题目

leetcode-222 给出一个完全二叉树，求出该树的节点个数。

1
2
3
4
5
6
7
8
输入: 
    1
   / \
  2   3
 / \  /
4  5 6

输出: 6

思路

完全二叉树，是由满二叉树改变而来的，满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。

我们可以比对左右子树的高度（遍历左右子树的左节点）：
- 若左子树高于右子树，我们可以断言右子树是满二叉树。
- 若右子树高于左子树，我们可以断言左子树是满二叉树。

而对于满二叉树的一端的节点数是很好求的，用公式2^n - 1 即可。而另一子树肯定也是完全二叉树，所以我们可以递归的求另一子树的节点数。

左子树高于右子树

右子树高于左子树
下面来看下具体的实现

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static int countNodes(TreeNode node) {

        if(node == null) return 0;
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        int sum = 0;
        if(leftHeight > rightHeight) {
            //右子树是个满二叉树
            sum = sum + (int)Math.pow(2,rightHeight) - 1 + 1;
            sum = sum + countNodes(node.left);
        }else {
            //左子树是满二叉树
            sum = sum + (int)Math.pow(2,leftHeight) - 1 + 1;
            sum = sum + countNodes(node.right);
        }

        return sum;
    }

    public static int getHeight(TreeNode node)  {

        int height = 0;
        while(node != null) {
            height++;
            node = node.left;
        }
        return height;
    }