如何解决OCaml计算多叉树高度时的模式匹配与类型报错问题

默认你使用的多叉树类型定义如下：

type 'a gt = Node of 'a * 'a gt list

三版代码的错误原因 #

• 第一版代码
  你仅显式匹配了子节点列表长度为0、1、2的三种情况，多叉树的子节点列表允许任意长度，所有长度≥3的场景都没有覆盖，因此编译器会报匹配不完整警告，你的测试用例中c节点有3个子节点，运行时直接触发匹配失败异常。
• 第二版代码
  List.map height' xs会将所有子节点转换为对应高度的int list类型，但OCaml原生max函数仅接收两个int类型的入参，你只给max传入了一个列表参数，返回的是等待第二个参数的偏函数，和预期的int类型不符，因此报类型错误。
• 第三版代码
  匹配分支中的t2是首子节点t1之后剩余的子节点列表，类型为'a gt list，但height函数要求入参是单个'a gt类型的树节点，参数类型不匹配，因此编译失败，同时该版本的高度计算逻辑本身也不符合多叉树高度定义。

正确实现 #

多叉树的高度定义为：当前节点高度 = 1 + 所有子节点高度的最大值，没有子节点时子节点最大高度为0，刚好对应叶子节点高度为1。我们可以用List.fold_left遍历子节点列表直接计算最大高度，实现如下：

let rec height tr =
  match tr with
  | Node (_, children) -> 
    1 + List.fold_left (fun current_max child -> max current_max (height child)) 0 children

验证测试 #

你给出的测试用例运行结果为4，符合预期：

let t : char gt =
Node('a',
     [Node('b',[]);
     Node('c',
      [Node('d',
        [Node('e',[])]);
      Node('f',[]);
      Node('g',[])])
     ]);;

height t;;
(* 输出：- : int = 4 *)

内容的提问来源于stack exchange，提问作者eznora