Haskell 最左边最深的树节点

Question

假设我有一个二叉树结构定义为

data IntTree = Empty | Node Int IntTree IntTree

和树

Node 0 (Node 1 Empty Empty)(Node 2 (Node 3 Empty Empty)(Node 4 Empty Empty))

如何提取最左边最深的节点（即Node 3 Empty Empty）？

Answer 1

您应该利用递归并定义一个返回节点深度的辅助函数，然后为每个 innode 选择最深的子节点。这样的函数看起来像：

leftmostDeep : IntTree -> IntTree
leftmostDeep = fst . go
    where go n@(Node _ Empty Empty) = (n, 0)
          go n@(Node _ Empty r) = let (nr, dr) = go r in (nr, dr+1)
          go n@(Node _ l Empty) = let (nl, dl) = go l in (nl, dl+1)
          go (Node l r) = …
              where (na, da) = go l
              where (nb, db) = go r

其中，…被留作练习。这应该确定哪个项目最深，并且作为决胜局，返回左子树。您还应该将该节点的深度增加一。