完全二叉树的节点个数

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

完全二叉树 & 满二叉树

首先介绍一下「完全二叉树」和「满二叉树」的区别！

• 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树
• 若设二叉树的深度为 h，除第 h 层外，其它各层 (1 ～ h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树

下面给出图，可以更加明显的看出区别：

对于求「满二叉树」的节点个数，这里有一个公式：$n=2^{depth}-1$$n=2^{depth}-1$，其中 $depth$$depth$ 为树的深度

上图中的满二叉树的深度为 4，所以其节点个数为：$n=2^4-1=15$$n=2^4-1=15$

今天要介绍的题目就是基于这个原理！

问题分析

对于「完全二叉树」，一定存在是「满二叉树」的子树

如上图所示，三角形框出来的子树就是「满二叉树」

对于这些是「满二叉树」的子树，求节点个数不需要遍历，直接利用公式即可！

现在存在一个问题：怎么判断子树是「满二叉树」呢？

• 只需要求出「左高」和「右高」，相等即为「满二叉树」

左高：顾名思义，一直通过左孩子节点求出来的高度；右高：顾名思义，一直通过右孩子节点求出来的高度

描述的比较抽象，直接看图：

其中绿色路径就是「左高」，为 4；橙色路径就是「右高」，为 3

所以以 0 为根节点的树不是「满二叉树」，但是以 1 和 5 为根节点的树是「满二叉树」

代码实现

下面给出完整代码：

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int lh = 0, rh = 0;
    TreeNode left = root, right = root;
    // 求左高
    while (left != null) {
        left = left.left;
        lh++;
    }
    // 求右高
    while (right != null) {
        right = right.right;
        rh++;
    }
    // 以 root 为根节点的树是「满二叉树」
    if (lh == rh) return (int) Math.pow(2, lh) - 1;
    // 否则，按照正常方式遍历
    return countNodes(root.left) + countNodes(root.right) + 1;
}