P56 - 判断二叉树是否对称

2026-09-07 00:00    #Haskell   #99题   #二叉树  

P56 - 判断二叉树是否对称

Symmetric binary trees

官方模块：Problems.P56　核心函数：symmetric

← P55 完全平衡二叉树 | P57 二叉搜索树 →

题目描述

只比较树的结构，不比较节点值。若左子树和右子树互为镜像，则整棵树对称。

函数签名

1symmetric :: Tree a -> Bool

实现

方法一：镜像递归比较

1symmetric :: Tree a -> Bool
2symmetric Empty                 = True
3symmetric (Branch _ left right) = mirror left right
4
5mirror :: Tree a -> Tree b -> Bool
6mirror Empty Empty = True
7mirror (Branch _ l r) (Branch _ l' r') =
8  mirror l r' && mirror r l'
9mirror _ _ = False

mirror 的两个类型参数可以不同，说明判定完全不关心节点值。每个节点至多访问一次，O(n)。

方法二：镜像路径集合

 1import qualified Data.Set as Set
 2
 3symmetric :: Tree a -> Bool
 4symmetric tree = all hasMirror paths
 5  where
 6    paths = nodePaths tree
 7    pathSet = Set.fromList paths
 8    hasMirror path = Set.member (map not path) pathSet
 9
10nodePaths :: Tree a -> [[Bool]]
11nodePaths = walk []
12  where
13    walk _ Empty = []
14    walk reversedPath (Branch _ left right) =
15      reverse reversedPath
16      : walk (False : reversedPath) left
17      ++ walk (True : reversedPath) right

用 False、True 分别表示向左和向右。若每个已存在节点路径的逐位镜像也存在，整棵树的形状就对称。集合方法不读取节点值。

方法三：翻转后比较

 1symmetric :: Tree a -> Bool
 2symmetric Empty = True
 3symmetric (Branch _ left right) = invertShape (shape left) == shape right
 4
 5shape :: Tree a -> Tree ()
 6shape Empty = Empty
 7shape (Branch _ left right) = Branch () (shape left) (shape right)
 8
 9invertShape :: Tree () -> Tree ()
10invertShape Empty = Empty
11invertShape (Branch () left right) =
12  Branch () (invertShape right) (invertShape left)

先擦除节点值，只保留 Tree () 的形状，再翻转左子树与右子树比较。因此签名不需要增加 Eq a 约束。

测试

1>>> symmetric (Branch 'x' (leaf 'a') (leaf 'b'))
2True
3>>> symmetric (Branch 'x' (leaf 'a') Empty)
4False
5>>> symmetric Empty
6True

参考