实现不可变二叉树的深度计算与叶子节点统计 -

题目

实现不可变二叉树的深度计算与叶子节点统计

信息

类型：问答
难度：⭐⭐

考点

不可变数据结构,递归与模式匹配,Option类型处理,函数组合

快速回答

核心实现要点：

使用sealed trait和case class定义不可变二叉树结构
通过递归和模式匹配实现depth和leafCount方法
空节点用Empty对象表示，避免null
使用Option安全处理可能缺失的值
函数组合实现maxDepthLeafCount

## 解析

问题背景

在函数式编程中，不可变数据结构和递归是核心概念。本题要求实现一个不可变二叉树，并完成深度计算和叶子节点统计功能，考察候选人处理递归数据结构、模式匹配和函数组合的能力。

原理说明

1. 不可变数据结构：所有操作返回新实例而非修改原数据，符合函数式编程无副作用原则
2. 递归处理：树形结构天然适合递归遍历，通过分解子问题简化计算
3. 模式匹配：Scala的match表达式可优雅处理不同节点类型
4. Option类型：安全处理可能缺失的值，避免NullPointerException

代码实现

// 1. 定义不可变二叉树ADT
sealed trait Tree[+T]
case object Empty extends Tree[Nothing]
case class Node[T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]

// 2. 实现计算逻辑
object Tree {
  // 计算最大深度
  def depth[T](tree: Tree[T]): Int = tree match {
    case Empty => 0
    case Node(_, left, right) => 1 + math.max(depth(left), depth(right))
  }

  // 统计叶子节点数量
  def leafCount[T](tree: Tree[T]): Int = tree match {
    case Empty => 0
    case Node(_, Empty, Empty) => 1  // 叶子节点
    case Node(_, left, right) => leafCount(left) + leafCount(right)
  }

  // 组合函数：获取深度和叶子数
  def maxDepthLeafCount[T](tree: Tree[T]): Option[(Int, Int)] = 
    if (tree == Empty) None
    else Some((depth(tree), leafCount(tree)))
}

// 使用示例
val tree = Node(1, 
  Node(2, Node(4, Empty, Empty), Empty),
  Node(3, Empty, Node(5, Empty, Empty))
)

Tree.depth(tree)       // 返回3
Tree.leafCount(tree)   // 返回3
Tree.maxDepthLeafCount(tree) // Some((3,3))

最佳实践

ADT设计：使用sealed trait确保编译期穷尽模式检查
空值处理：用Empty单例替代null，消除空指针风险
尾递归优化：对于深度大的树，可将depth改为尾递归版本（需使用accumulator）
类型参数化：Tree[+T]支持协变，增强类型灵活性

常见错误

错误类型	错误示例	修正方案
未处理空树	`case Node(v,l,r) => ...` 缺少Empty分支	补全Empty匹配分支
错误识别叶子节点	`case Node(_,l,r) if l==null => ...`	使用`case Node(_,Empty,Empty)`
副作用操作	在递归中修改外部变量	改用纯函数返回值累加

扩展知识

Catamorphisms：可通过fold函数泛化递归模式

def fold[T,U](t: Tree[T])(f: T => U)(g: (U,U) => U): U = t match {
  case Empty => f(null.asInstanceOf[T])
  case Node(v,l,r) => g(f(v), g(fold(l)(f)(g), fold(r)(f)(g)))
}