Haskell二叉树路径函数返回结果缺失叶节点值，求问题原因

哈哈，这个问题我当初写Haskell二叉树路径遍历的时候也踩过！你的结果里缺失叶节点，大概率是递归终止条件或者路径积累的逻辑出了问题——具体来说，你在处理叶节点的时候，没有把叶节点本身的值添加到路径里。

错误原因拆解 #

你得到的结果[[5,4],[5,4],[5,3],[5,3]]说明：每一条路径都停在了叶节点的父节点上，完全没把叶节点的值加进去。比如对应5→4→1的路径，你只保留了[5,4]，漏掉了最后的1。

这种情况最常见的错误写法是这样的（假设你用了累加器辅助函数）：

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

-- 错误的实现
paths :: Tree a -> [[a]]
paths t = helper t []
  where
    helper Empty _ = []
    -- 这里是核心错误：叶节点返回的是积累的父路径，没把当前节点x加进去
    helper (Node x Empty Empty) acc = [acc]
    helper (Node x left right) acc = 
      helper left (acc ++ [x]) ++ helper right (acc ++ [x])

当处理叶节点（比如Node 1 Empty Empty）时，函数直接返回了之前积累的路径[5,4]，而没有把当前的1追加进去，自然就丢失了叶节点。

正确的实现方式 #

我们需要保证叶节点的值被添加到路径末尾，同时空节点不产生无效路径。这里有两种常用的正确写法：

写法1：直接递归（直观易读） #

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

paths :: Tree a -> [[a]]
paths Empty = []
-- 叶节点返回只包含自身的单元素列表，作为路径的终点
paths (Node x Empty Empty) = [[x]]
-- 非叶节点：把当前节点值加到子树路径的开头，拼接成完整路径
paths (Node x left right) = map (x:) (paths left) ++ map (x:) (paths right)

写法2：累加器优化（更高效） #

如果树比较大，直接递归的列表拼接会有性能损耗，用累加器可以避免这个问题：

paths :: Tree a -> [[a]]
paths t = helper t []
  where
    helper Empty _ = []
    -- 叶节点：把当前值加到积累路径的末尾，形成完整路径
    helper (Node x Empty Empty) acc = [acc ++ [x]]
    -- 非叶节点：把当前值加入积累路径，继续遍历左右子树
    helper (Node x left right) acc = 
      helper left (acc ++ [x]) ++ helper right (acc ++ [x])

测试验证 #

假设你的测试二叉树是这样的：

testTree :: Tree Int
testTree = Node 5
            (Node 4
              (Node 1 Empty Empty)
              (Node 2 Empty Empty))
            (Node 3
              (Node 3 Empty Empty)
              (Node 4 Empty Empty))

调用paths testTree就会得到你预期的结果：

[[5,4,1],[5,4,2],[5,3,3],[5,3,4]]

总结 #

核心问题就是叶节点的处理逻辑：你必须把叶节点的值加入到路径中，而不是直接返回父节点的路径。只要修正叶节点的返回值，把当前节点的值追加到路径末尾，就能得到正确的结果啦！

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