使用Go語言判斷二叉樹是否對(duì)稱的方法小結(jié)
更新時(shí)間：2025年07月29日 08:24:05 作者：程序員愛釣魚
二叉樹Binary Tree一種特殊的樹,是結(jié)點(diǎn)的一個(gè)有限集合,且所有結(jié)點(diǎn)最多有2個(gè)子結(jié)點(diǎn),即度只能是0,1,2,判斷二叉樹是否對(duì)稱需比較左右子樹結(jié)構(gòu)與值,遞歸法直接對(duì)比子節(jié)點(diǎn),迭代法用隊(duì)列模擬遞歸,本文通過代碼示例講解的非常詳細(xì),需要的朋友可以參考下
給定一棵二叉樹，判斷這棵樹是否是對(duì)稱的。對(duì)稱的含義是：這棵樹的左子樹和右子樹在結(jié)構(gòu)上是鏡像對(duì)稱的，且對(duì)應(yīng)節(jié)點(diǎn)的值相等。
一、示例
示例 1：
????1 ???/?\ ??2???2 ?/?\?/?\ 3??4?4??3 輸出：true
示例 2：
????1 ???/?\ ??2???2 ???\???\ ???3????3 輸出：false
二、應(yīng)用場(chǎng)景
- • 用戶界面或布局中驗(yàn)證左右對(duì)稱性
- • 算法競(jìng)賽題目或筆試面試?？?/li>
- • 樹結(jié)構(gòu)可視化或分析工具中，對(duì)稱性判斷用于簡(jiǎn)化處理
三、解題思路
本問題的關(guān)鍵在于：比較樹的左子樹和右子樹是否鏡像對(duì)稱。
我們可以采用兩種方法：
方法一：遞歸判斷
判斷左右子樹是否滿足以下三個(gè)條件：
- 左子樹的左子樹和右子樹的右子樹對(duì)稱；
- 左子樹的右子樹和右子樹的左子樹對(duì)稱；
- 當(dāng)前兩個(gè)節(jié)點(diǎn)值相同。
方法二：迭代判斷（借助隊(duì)列）
使用隊(duì)列存儲(chǔ)成對(duì)的節(jié)點(diǎn)，每次成對(duì)彈出并比較：
- • 若都為空，繼續(xù)；
- • 若一個(gè)為空另一個(gè)不為空 → 不對(duì)稱；
- • 值不相等 → 不對(duì)稱；
- • 否則將子節(jié)點(diǎn)成對(duì)壓入隊(duì)列，繼續(xù)判斷。
四、Go語言實(shí)現(xiàn)
1. 數(shù)據(jù)結(jié)構(gòu)定義
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. 方法二：迭代法（使用隊(duì)列）
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
}
五、測(cè)試樣例
func?main()?{
????//?構(gòu)建對(duì)稱二叉樹
????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("遞歸判斷結(jié)果：",?isSymmetric(root))???????????//?true
????fmt.Println("迭代判斷結(jié)果：",?isSymmetricIterative(root))?//?true
}
六、復(fù)雜度分析
| 方式 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|---|
| 遞歸法 | O(n) | O(h) |
| 迭代法 | O(n) | O(n) |
- n 表示節(jié)點(diǎn)數(shù)量；
- h 表示樹的高度（遞歸調(diào)用棧的深度）；
- 迭代方法使用了隊(duì)列，需要額外 O(n) 空間存儲(chǔ)節(jié)點(diǎn)。
七、可視化理解
將二叉樹從中心線對(duì)折，看左、右兩部分是否完全重合，節(jié)點(diǎn)值是否相等。
鏡像對(duì)稱結(jié)構(gòu)滿足：
left.Left==right.Rightleft.Right==right.Left
八、變種與擴(kuò)展
- 1. 判斷 N 叉樹是否鏡像對(duì)稱：需要成對(duì)比較左右子節(jié)點(diǎn)；
- 2. 輸出是否對(duì)稱的最小修改操作：可結(jié)合動(dòng)態(tài)規(guī)劃思想；
- 3. 判斷對(duì)稱層級(jí)：例如僅判斷前兩層是否對(duì)稱。
九、總結(jié)
| 內(nèi)容 | 說明 |
|---|---|
| 核心判斷條件 | 左右子樹是否鏡像結(jié)構(gòu)，對(duì)應(yīng)節(jié)點(diǎn)值是否相等 |
| 遞歸 vs 迭代 | 遞歸寫法更直觀，迭代適合大樹或避免棧溢出 |
| 技巧點(diǎn) | 左-右子樹配對(duì)判斷，使用隊(duì)列模擬遞歸過程 |
| 實(shí)用價(jià)值 | 面試高頻，掌握樹結(jié)構(gòu)對(duì)稱性判斷通用技巧 |
以上就是使用Go語言判斷二叉樹是否對(duì)稱的方法小結(jié)的詳細(xì)內(nèi)容，更多關(guān)于Go判斷二叉樹對(duì)稱的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
go語言中regexp正則表達(dá)式的操作實(shí)現(xiàn)
regexp包支持對(duì)字符串的匹配、搜索和替換,它基于RE2正則表達(dá)式引擎,該包提供了多個(gè)函數(shù)來編譯正則表達(dá)式并進(jìn)行匹配、查找、替換等操作,下面就來詳細(xì)的介紹一下regexp正則表達(dá)式的實(shí)現(xiàn),感興趣的可以了解一下2025-09-09
Go與Redis實(shí)現(xiàn)分布式互斥鎖和紅鎖
這篇文章主要介紹了Go與Redis實(shí)現(xiàn)分布式互斥鎖和紅鎖，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-09-09
Go語言MySQLCURD數(shù)據(jù)庫(kù)操作示例詳解
這篇文章主要為大家介紹了Go語言MySQLCURD數(shù)據(jù)庫(kù)操作示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-12-12
Golang WebView跨平臺(tái)的桌面應(yīng)用庫(kù)的使用
Golang WebView是一個(gè)強(qiáng)大的桌面應(yīng)用庫(kù),本文介紹了Golang WebView的特點(diǎn)和使用方法,并列舉示例詳細(xì)的介紹了其在實(shí)際項(xiàng)目中的應(yīng)用,具有一定的參考價(jià)值,感興趣的可以了解一下2024-03-03
Golang使用Apache PLC4X連接modbus的示例代碼
Modbus是一種串行通信協(xié)議,是Modicon公司于1979年為使用可編程邏輯控制器（PLC）通信而發(fā)表,這篇文章主要介紹了Golang使用Apache PLC4X連接modbus的示例代碼,需要的朋友可以參考下2024-07-07
Go使用context控制協(xié)程取消的實(shí)戰(zhàn)案例
在并發(fā)編程中,合理地控制協(xié)程的生命周期是保證程序穩(wěn)定性和資源可控使用的關(guān)鍵,Go語言標(biāo)準(zhǔn)庫(kù)中的context包正是為了解決這一問題而生,它為我們提供了取消信號(hào)、超時(shí)控制、請(qǐng)求作用域的值傳遞等功能,本文將通過一個(gè)實(shí)際案例,演示如何使用context控制協(xié)程的取消2025-08-08
本文主要介紹了Golang實(shí)現(xiàn)單鏈表的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
這篇文章主要為大家詳細(xì)介紹了Go語言中context用法的相關(guān)知識(shí)，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價(jià)值，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-07-07
go語言中使用ent做關(guān)聯(lián)查詢的示例詳解
go語言的ent框架是facebook開源的ORM框架,是go語言開發(fā)中的常用框架,而關(guān)聯(lián)查詢又是日常開發(fā)中的常見數(shù)據(jù)庫(kù)操作,故文本給出一個(gè)使用ent做關(guān)聯(lián)查詢的使用示例,需要的朋友可以參考下2024-02-02
Golang?Compare?And?Swap算法詳細(xì)介紹
CAS算法是一種有名的無鎖算法。無鎖編程，即不使用鎖的情況下實(shí)現(xiàn)多線程之間的變量同步，也就是在沒有線程被阻塞的情況下實(shí)現(xiàn)變量的同步，所以也叫非阻塞同步Non-blocking?Synchronization2022-10-10