TNotes.leetcode

Appearance

0222. 完全二叉树的节点个数【简单】

0222. 完全二叉树的节点个数【简单】 ​

1. 📝 题目描述 ​

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

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

示例 1：

img

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

示例 2：

txt
输入：root = []
输出：0

示例 3：

txt
输入：root = [1]
输出：1

提示：

  • 树中节点的数目范围是[0, 5 * 10^4]
  • 0 <= Node.val <= 5 * 10^4
  • 题目数据保证输入的树是 完全二叉树

进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

2. 🎯 s.1 - 暴力解法普通递归遍历 ​

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */

var countNodes = function (root) {
  if (!root) return 0

  return 1 + countNodes(root.left) + countNodes(root.right)
}
  • 时间复杂度：O(n)，需要访问每个节点
  • 空间复杂度：O(log⁡n)，递归调用栈的深度

算法思路：

  • 递归遍历整棵树，计算节点总数
  • 递归公式：节点总数 = 1（当前节点） + 左子树节点数 + 右子树节点数
  • 这是最直接的解法，但没有利用完全二叉树的特性

3. 🎯 s.2 - 利用完全二叉树特性优化递归 ​

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function (root) {
  if (!root) return 0

  // 获取树的高度（最左侧路径）
  const getHeight = (node) => {
    let height = 0
    while (node) {
      height++
      node = node.left
    }
    return height
  }

  const leftHeight = getHeight(root.left)
  const rightHeight = getHeight(root.right)

  if (leftHeight === rightHeight) {
    // 如果左右高度相等，左子树必是满二叉树，用公式 2^h 直接计算，递归右子树
    return (1 << leftHeight) + countNodes(root.right)
  } else {
    // 如果左右高度不等，右子树必是满二叉树，用公式 2^h 直接计算，递归左子树
    return (1 << rightHeight) + countNodes(root.left)
  }
}
  • 时间复杂度：O(log2⁡n)，每次递归需要 O(log⁡n) 时间计算高度，最多递归 O(log⁡n) 次
  • 空间复杂度：O(log⁡n)，递归调用栈的深度

算法思路：

  • 利用完全二叉树的性质：除最后一层外，其他层都是满的
  • 比较左右子树的高度（沿着最左路径计算）
  • 如果左右高度相等，左子树必是满二叉树，用公式 2h 直接计算，递归右子树
  • 如果左右高度不等，右子树必是满二叉树，用公式计算，递归左子树
  • 位运算 1 << h 等价于 2h，效率更高

4. 🔗 引用 ​

Discussions