222. 完全二叉树的节点个数

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

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例:

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

输出: 6

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-complete-tree-nodes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一：递归分别计算左右子树的节点个数 再加上1，就是当前树的节点个数。 需要递归每个元素，代码如下，此方法时间复杂度为O（N）。

1
2
3
4
5

    public int countNodes(TreeNode root) {

        if (root == null) return 0;
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

思路二：以上方法中，适用于任意二叉树，没有用到完全二叉树的特点，效率较差。 故我们在此基础上做一些优化。 heigh方法计算传入node的高度，如果left的高度 == right的高度，则左子树一定是满二叉树，则总节点个数等于左子树个数 + 递归计算右子树节点个数 + 1；

若left的高度 != right的高度， 则右子树一定是满二叉树，则总节点个数等于递归计算左子树个数 + 右子树节点个数 + 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

    public int countNodes1(TreeNode root) {
        if (root == null) return 0;

        int height_l = height(root.left);
        int height_r = height(root.right);

        if (height_l == height_r){
            // 左子树一定是满二叉树
            return (1 << height_l) + countNodes(root.right);
        }else {
            // 右子树一定是满二叉树
            return (1 << height_r) + countNodes(root.left);
        }
    }

    public int height(TreeNode root){
        if (root == null) return 0;

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

        return height;
    }