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

222. 完全二叉树的节点个数 - 力扣（LeetCode）

题目描述

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

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

题目示例

在这里插入图片描述

输入：root = [1,2,3,4,5,6]
输出：6

解题思路

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
在这里插入图片描述
可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。

这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。

在这里插入图片描述

参考代码

class Solution {
    public int countNodes(TreeNode root) {
        // 普通二叉树使用任何方式都可以计算节点个数
        // 但是这是完全二叉树，目的很明确，让你用完全二叉树的特性
        // 利用完全二叉树的特性来求节点个数
        // 满二叉树，最左侧深度和最右侧深度是一样的
        // 完全二叉树内总有一个满二叉树
        if(root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0;
        int rightDepth = 0;
        while(left != null) {
            leftDepth++;
            left = left.left;
        }
        while(right != null) {
            rightDepth++;
            right = right.right;
        }
        if(leftDepth == rightDepth) {
            return (2 << leftDepth) - 1;
        }
        int leftNum = countNodes(root.left);
        int rightNum = countNodes(root.right);
        return leftNum + rightNum + 1;
    }
}