关于算法:如何计算完全二叉树的节点数

读完本文，你能够去力扣拿下如下题目：

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

———–

如果让你数一下一棵一般二叉树有多少个节点，这很简略，只有在二叉树的遍历框架上加一点代码就行了。

然而，如果给你一棵齐全二叉树，让你计算它的节点个数，你会不会？算法的工夫复杂度是多少？这个算法的工夫复杂度应该是 O(logN*logN)，如果你心中的算法没有达到高效，那么本文就是给你写的。

首先要明确一下两个对于二叉树的名词「齐全二叉树」和「满二叉树」。

咱们说的 齐全二叉树 如下图，每一层都是紧凑靠左排列的：

咱们说的 满二叉树 如下图，是一种非凡的齐全二叉树，每层都是是满的，像一个稳固的三角形：

说句题外话，对于这两个定义，中文语境和英文语境仿佛有点区别，咱们说的齐全二叉树对应英文 Complete Binary Tree，没有问题。然而咱们说的满二叉树对应英文 Perfect Binary Tree，而英文中的 Full Binary Tree 是指一棵二叉树的所有节点要么没有孩子节点，要么有两个孩子节点。如下：

以上定义出自 wikipedia，这里就是顺便一提，其实名词叫什么都无所谓，重要的是算法操作。本文就按咱们中文的语境，记住「满二叉树」和「齐全二叉树」的区别，等会会用到。

一、思路剖析

当初回归正题，如何求一棵齐全二叉树的节点个数呢？

// 输出一棵齐全二叉树，返回节点总数
int countNodes(TreeNode root);

如果是一个 一般 二叉树，显然只有向上面这样遍历一边即可，工夫复杂度 O(N)：

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

那如果是一棵 满二叉树，节点总数就和树的高度呈指数关系：

public int countNodes(TreeNode root) {
    int h = 0;
    // 计算树的高度
    while (root != null) {
        root = root.left;
        h++;
    }
    // 节点总数就是 2^h - 1
    return (int)Math.pow(2, h) - 1;
}

齐全 二叉树比一般二叉树非凡，但又没有满二叉树那么非凡，计算它的节点总数，能够说是一般二叉树和齐全二叉树的联合版，先看代码：

public int countNodes(TreeNode root) {
    TreeNode l = root, r = root;
    // 记录左、右子树的高度
    int hl = 0, hr = 0;
    while (l != null) {
        l = l.left;
        hl++;
    }
    while (r != null) {
        r = r.right;
        hr++;
    }
    // 如果左右子树的高度雷同，则是一棵满二叉树
    if (hl == hr) {return (int)Math.pow(2, hl) - 1;
    }
    // 如果左右高度不同，则依照一般二叉树的逻辑计算
    return 1 + countNodes(root.left) + countNodes(root.right);
}

联合方才针对满二叉树和一般二叉树的算法，下面这段代码应该不难理解，就是一个联合版，然而 其中升高工夫复杂度的技巧是十分奥妙的。

二、复杂度剖析

结尾说了，这个算法的工夫复杂度是 O(logN*logN)，这是怎么算进去的呢？

直觉感觉如同最坏状况下是 O(N\*logN) 吧，因为之前的 while 须要 logN 的工夫，最初要 O(N) 的工夫向左右子树递归：

return 1 + countNodes(root.left) + countNodes(root.right);

关键点在于，这两个递归只有一个会真的递归上来，另一个肯定会触发 hl == hr 而立刻返回，不会递归上来。

为什么呢？起因如下：

一棵齐全二叉树的两棵子树，至多有一棵是满二叉树：

看图就显著了吧，因为齐全二叉树的性质，其子树肯定有一棵是满的，所以肯定会触发 hl == hr，只耗费 O(logN) 的复杂度而不会持续递归。

综上，算法的递归深度就是树的高度 O(logN)，每次递归所破费的工夫就是 while 循环，须要 O(logN)，所以总体的工夫复杂度是 O(logN*logN)。

所以说，「齐全二叉树」这个概念还是有它存在的起因的，不仅实用于数组实现二叉堆，而且连计算节点总数这种看起来简略的操作都有高效的算法实现。