使用Go語言判斷二叉樹是否對稱的方法小結
更新時間：2025年07月29日 08:24:05 作者：程序員愛釣魚
二叉樹Binary Tree一種特殊的樹,是結點的一個有限集合,且所有結點最多有2個子結點,即度只能是0,1,2,判斷二叉樹是否對稱需比較左右子樹結構與值,遞歸法直接對比子節(jié)點,迭代法用隊列模擬遞歸,本文通過代碼示例講解的非常詳細,需要的朋友可以參考下
給定一棵二叉樹，判斷這棵樹是否是對稱的。對稱的含義是：這棵樹的左子樹和右子樹在結構上是鏡像對稱的，且對應節(jié)點的值相等。
一、示例
示例 1：
????1 ???/?\ ??2???2 ?/?\?/?\ 3??4?4??3 輸出：true
示例 2：
????1 ???/?\ ??2???2 ???\???\ ???3????3 輸出：false
二、應用場景
- • 用戶界面或布局中驗證左右對稱性
- • 算法競賽題目或筆試面試?？?/li>
- • 樹結構可視化或分析工具中，對稱性判斷用于簡化處理
三、解題思路
本問題的關鍵在于：比較樹的左子樹和右子樹是否鏡像對稱。
我們可以采用兩種方法：
方法一：遞歸判斷
判斷左右子樹是否滿足以下三個條件：
- 左子樹的左子樹和右子樹的右子樹對稱；
- 左子樹的右子樹和右子樹的左子樹對稱；
- 當前兩個節(jié)點值相同。
方法二：迭代判斷（借助隊列）
使用隊列存儲成對的節(jié)點，每次成對彈出并比較：
- • 若都為空，繼續(xù)；
- • 若一個為空另一個不為空 → 不對稱；
- • 值不相等 → 不對稱；
- • 否則將子節(jié)點成對壓入隊列，繼續(xù)判斷。
四、Go語言實現(xiàn)
1. 數(shù)據(jù)結構定義
package?main
import?"fmt"
type?TreeNode?struct?{
????Val???int
????Left??*TreeNode
????Right?*TreeNode
}
2. 方法一：遞歸法
func?isSymmetric(root?*TreeNode)?bool?{
????if?root?==?nil?{
????????return?true
????}
????return?isMirror(root.Left,?root.Right)
}
func?isMirror(left,?right?*TreeNode)?bool?{
????if?left?==?nil?&&?right?==?nil?{
????????return?true
????}
????if?left?==?nil?||?right?==?nil?{
????????return?false
????}
????if?left.Val?!=?right.Val?{
????????return?false
????}
????return?isMirror(left.Left,?right.Right)?&&?isMirror(left.Right,?right.Left)
}
3. 方法二：迭代法（使用隊列）
func?isSymmetricIterative(root?*TreeNode)?bool?{
????if?root?==?nil?{
????????return?true
????}
????queue?:=?[]*TreeNode{root.Left,?root.Right}
????for?len(queue)?>?0?{
????????left?:=?queue[0]
????????right?:=?queue[1]
????????queue?=?queue[2:]
????????if?left?==?nil?&&?right?==?nil?{
????????????continue
????????}
????????if?left?==?nil?||?right?==?nil?||?left.Val?!=?right.Val?{
????????????return?false
????????}
????????queue?=?append(queue,?left.Left,?right.Right)
????????queue?=?append(queue,?left.Right,?right.Left)
????}
????return?true
}
五、測試樣例
func?main()?{
????//?構建對稱二叉樹
????root?:=?&TreeNode{Val:?1}
????root.Left?=?&TreeNode{Val:?2}
????root.Right?=?&TreeNode{Val:?2}
????root.Left.Left?=?&TreeNode{Val:?3}
????root.Left.Right?=?&TreeNode{Val:?4}
????root.Right.Left?=?&TreeNode{Val:?4}
????root.Right.Right?=?&TreeNode{Val:?3}
????fmt.Println("遞歸判斷結果：",?isSymmetric(root))???????????//?true
????fmt.Println("迭代判斷結果：",?isSymmetricIterative(root))?//?true
}
六、復雜度分析
| 方式 | 時間復雜度 | 空間復雜度 |
|---|---|---|
| 遞歸法 | O(n) | O(h) |
| 迭代法 | O(n) | O(n) |
- n 表示節(jié)點數(shù)量；
- h 表示樹的高度（遞歸調用棧的深度）；
- 迭代方法使用了隊列，需要額外 O(n) 空間存儲節(jié)點。
七、可視化理解
將二叉樹從中心線對折，看左、右兩部分是否完全重合，節(jié)點值是否相等。
鏡像對稱結構滿足：
left.Left==right.Rightleft.Right==right.Left
八、變種與擴展
- 1. 判斷 N 叉樹是否鏡像對稱：需要成對比較左右子節(jié)點；
- 2. 輸出是否對稱的最小修改操作：可結合動態(tài)規(guī)劃思想；
- 3. 判斷對稱層級：例如僅判斷前兩層是否對稱。
九、總結
| 內容 | 說明 |
|---|---|
| 核心判斷條件 | 左右子樹是否鏡像結構，對應節(jié)點值是否相等 |
| 遞歸 vs 迭代 | 遞歸寫法更直觀，迭代適合大樹或避免棧溢出 |
| 技巧點 | 左-右子樹配對判斷，使用隊列模擬遞歸過程 |
| 實用價值 | 面試高頻，掌握樹結構對稱性判斷通用技巧 |
以上就是使用Go語言判斷二叉樹是否對稱的方法小結的詳細內容，更多關于Go判斷二叉樹對稱的資料請關注腳本之家其它相關文章！
相關文章
詳解用Go語言實現(xiàn)工廠模式(Golang經典編程案例)
這篇文章主要介紹了詳解用Go語言實現(xiàn)工廠模式(Golang經典編程案例),文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
go浮點數(shù)轉字符串保留小數(shù)點后N位的完美解決方法
這篇文章主要介紹了go浮點數(shù)轉字符串保留小數(shù)點后N位解決辦法,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-05-05
這篇文章主要介紹了如何利用Go語言實現(xiàn)LRU?Cache，LRU是Least?Recently?Used的縮寫，是一種操作系統(tǒng)中常用的頁面置換算法，下面我們一起進入文章了解更多內容吧,需要的朋友可以參考一下2022-03-03
go?mod?tidy報錯:zip:?not?a?valid?zip?file解決辦法
這篇文章主要給大家介紹了關于go?mod?tidy報錯:zip:?not?a?valid?zip?file的解決辦法,go mod是進行代碼管理，這錯誤是因為本地分支和遠程分支沖突,本文通過代碼介紹的非常詳細,需要的朋友可以參考下2024-01-01
在golang中字符串的拼接方式有多種,本文將會介紹比較常用的幾種方式,并且對各種方式進行壓測,具有一定的參考價值,感興趣的可以了解一下2024-01-01
橋接是一種結構型設計模式，可將業(yè)務邏輯或一個大類拆分為不同的層次結構，從而能獨立地進行開發(fā)，本文將通過代碼示例詳細給大家介紹一下Golang橋接模式,需要的朋友可以參考下2023-06-06
在Golang中，異常處理是非常重要的一部分，能夠有效地控制和處理代碼中的異常情況。通過Golang的異常處理機制，可以優(yōu)雅地捕獲和處理異常，保障代碼的可靠性和穩(wěn)定性。同時，Golang還提供了豐富的工具和API，幫助開發(fā)者更加輕松地進行異常處理2023-04-04
在搭建項目中一般都會有確定項目根目錄的絕對路徑的需求,下面這篇文章主要給大家介紹了關于Golang實踐指南之獲取目錄文件列表的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-01-01
這篇文章主要為大家詳細介紹了Go語言中定時任務cron的設計與使用,文中的示例代碼講解詳細,對我們深入掌握Go語言有一定的幫助,需要的可以參考下2023-11-11
隨著互聯(lián)網的快速發(fā)展和數(shù)據(jù)交換的廣泛應用，各種數(shù)據(jù)格式的處理成為軟件開發(fā)中的關鍵問題，本文將介紹?Golang?中?JSON?編碼與解碼的相關知識，幫助大家了解其基本原理和高效應用，需要的可以收藏一下2023-05-05