描述

题目描述

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

示例
输入:{1,2,3} 
返回值:3

知识点:完全二叉树,递归
难度:⭐⭐⭐


题解

方法一:递归

解题思路:

完全二叉树的特性:

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

image-20210718170829660

image-20210718170917762

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

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

满二叉树计算公式: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):递归需要的栈空间