描述

题目描述

给定一棵完全二叉树的头节点head，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。

示例

输入：{1,2,3} 
返回值：3

知识点：完全二叉树，递归
难度：⭐⭐⭐

题解

方法一：递归

解题思路：

完全二叉树的特性：

1. 完全二叉树的左右子树中至少有一颗是满二叉树，叶子结点只能出现在最下两层
2. 最下层的叶子一定集中在左部连续位置，因此最深处一定在最左下角（可用来求子树深度）。如果倒数第二层出现叶子，则一定在右边且连续
3. 对于子树有两种情况：
   1. 情况1：若是左子树高度大，则右边子树一定是满的。
   2. 情况2：若是左右深度相同，则左边子树一定满的

根据以上几个完全二叉树的特性，通过遍历每个所有结点，根据不同情况统计结点数即可

我们可以通过递归，获取每个结点作为根的二叉树节点个数

满二叉树计算公式：2 ^ heigh

总的结点数 = 根节点 + 满二叉树节点个数 + 完全二叉树节点个数

算法流程：

• 定义递归函数功能：获取每个结点作为根的二叉树节点个数
• 先得到当前结点head的左右子树高度，根据左右子树高度分情况：
  • 情况1：左子树高度大于右子树高度，即当前结点head的右子树是满二叉树
    • 总的结点数 = 根节点 + 满二叉树节点个数（右子树） + 完全二叉树节点个数（左子树）
  • 情况2：左右子树高度相同，即当前结点head的左子树是满二叉树
    • 总的结点数 = 根节点 + 满二叉树节点个数（左子树） + 完全二叉树节点个数（右子树）

Java 版本代码如下：

import java.util.*;

public class Solution {
    // 递归函数功能：获取每个结点作为根的二叉树节点个数
    public int nodeNum(TreeNode head) {
        if(head == null) {
            return 0;
        }
        // 得到当前结点head的左右子树高度
        int left = getHeight(head.left);
        int right = getHeight(head.right);

        if(left != right) {
            // 情况1：左子树高度大于右子树高度，即当前结点head的右子树是满二叉树
            // 满二叉树计算公式：2 ^ heigh
            // 总的结点数 = 根节点 + 满二叉树节点个数（右子树） + 完全二叉树节点个数（左子树）
            return 1 + (int)Math.pow(2, right) - 1 + nodeNum(head.left);
        } else {
            // 情况2：左右子树高度相同，即当前结点head的左子树是满二叉树
            // 总的结点数 = 根节点 + 满二叉树节点个数（左子树） + 完全二叉树节点个数（右子树）
            return 1 + (int)Math.pow(2, left) - 1 + nodeNum(head.right);
        }
    }

    // 获取当前结点的深度
    public int getHeight(TreeNode root) {
        int count = 0;
        // 只需要计算左叶子结点深度就行
        while(root != null) {
            count++;
            root = root.left;
        }
        return count;
    }
}

复杂度分析：

时间复杂度 O((lgN^2))：每次到最左寻找最大深度时间为树的最大深度O(lgn)，对于不满的二叉树递归下去，递归复杂度是O(lgn)，相乘为O(lgn ^2)
空间复杂度 O(lgN)：递归所需要栈的最大深度，对于不满的二叉树的子树需要递归

方法二：暴力解法

虽然暴力解法可以实现，但是事件复杂度不符合要求

算法流程：

• 定义递归函数功能：获取每个结点作为根的二叉树节点个数
• 递归每个结点，统计节点数

Java 版本代码如下：

import java.util.*;

public class Solution {
    // 递归函数功能：获取每个结点作为根的二叉树节点个数
    public int nodeNum(TreeNode head) {
        if(head == null) {
            return 0;
        } 
        // 根节点非空, 算1个
        int res = 1;
        // 递归每个结点，递归加上左右孩子, 不用判空
        res += nodeNum(head.left);
        res += nodeNum(head.right);
        return res;
    }
}

复杂度分析：

时间复杂度 O(N)：需要递归每个结点
空间复杂度 O(N)：递归需要的栈空间