P68 - 根据中序和前序序列重建二叉树

In-order and pre-order sequences of binary trees
官方模块：Problems.P68　核心函数：inorder、preorder、ordersToTree

遍历

1inorder :: Tree a -> [a]
2inorder Empty = []
3inorder (Branch x left right) = inorder left ++ [x] ++ inorder right
4
5preorder :: Tree a -> [a]
6preorder Empty = []
7preorder (Branch x left right) = [x] ++ preorder left ++ preorder right

重建思路

前序首元素是根。在中序序列中找到根，其左侧长度就是左子树节点数；据此切分剩余前序序列，再递归重建两侧。题目约定节点值互不相同。

方法一：列表切分

 1ordersToTree :: Eq a => [a] -> [a] -> Maybe (Tree a)
 2ordersToTree [] [] = Just Empty
 3ordersToTree inorderValues (root:preorderValues) = do
 4  let (leftIn, rest) = break (== root) inorderValues
 5  rightIn <- case rest of
 6    _:xs -> Just xs
 7    []   -> Nothing
 8  let (leftPre, rightPre) = splitAt (length leftIn) preorderValues
 9  left  <- ordersToTree leftIn leftPre
10  right <- ordersToTree rightIn rightPre
11  pure (Branch root left right)
12ordersToTree _ _ = Nothing

方法二：中序位置索引

 1import qualified Data.Map.Strict as Map
 2
 3ordersToTreeFast :: Ord a => [a] -> [a] -> Maybe (Tree a)
 4ordersToTreeFast inorderValues preorderValues
 5  | length inorderValues /= length preorderValues = Nothing
 6  | Map.size positions /= length inorderValues = Nothing
 7  | otherwise = do
 8      (tree, rest) <- build 0 (length inorderValues - 1) preorderValues
 9      if null rest then Just tree else Nothing
10  where
11    positions = Map.fromList (zip inorderValues [0..])
12
13    build low high remaining
14      | low > high = Just (Empty, remaining)
15    build low high (root:rest) = do
16      position <- Map.lookup root positions
17      if position < low || position > high
18        then Nothing
19        else do
20          (left, afterLeft) <- build low (position - 1) rest
21          (right, afterRight) <- build (position + 1) high afterLeft
22          pure (Branch root left right, afterRight)
23    build _ _ [] = Nothing

中序值到位置的 Map 让每次根节点定位从线性查找降为 $O(\log n)$ ，同时用上下界表示子序列，避免重复执行 break 和 splitAt。

方法对比

方法	根位置查找	最坏复杂度
列表切分	`break` 线性扫描	O(n²)
位置索引	`Map.lookup`	O(n log n)

测试

 1>>> inorder tree1
 2"dbeacgf"
 3>>> preorder tree1
 4"abdecfg"
 5>>> ordersToTree (inorder tree1) (preorder tree1) == Just tree1
 6True
 7>>> ordersToTree "ab" "a"
 8Nothing
 9>>> ordersToTreeFast (inorder tree1) (preorder tree1) == Just tree1
10True

若把 Map 换成适合节点编号的数组，中序位置查找还可以进一步降为 $O(1)$ ，使整体达到 $O(n)$ 。

参考

← P67 括号字符串表示 | P69 点串表示 →