使用Go語(yǔ)言判斷二叉樹是否對(duì)稱的方法小結(jié)
更新時(shí)間：2025年07月29日 08:24:05 作者：程序員愛(ài)釣魚
二叉樹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ì)列模擬遞歸,本文通過(guò)代碼示例講解的非常詳細(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)化處理
三、解題思路
本問(wè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語(yǔ)言實(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)容 | 說(shuō)明 |
|---|---|
| 核心判斷條件 | 左右子樹是否鏡像結(jié)構(gòu)，對(duì)應(yīng)節(jié)點(diǎn)值是否相等 |
| 遞歸 vs 迭代 | 遞歸寫法更直觀，迭代適合大樹或避免棧溢出 |
| 技巧點(diǎn) | 左-右子樹配對(duì)判斷，使用隊(duì)列模擬遞歸過(guò)程 |
| 實(shí)用價(jià)值 | 面試高頻，掌握樹結(jié)構(gòu)對(duì)稱性判斷通用技巧 |
以上就是使用Go語(yǔ)言判斷二叉樹是否對(duì)稱的方法小結(jié)的詳細(xì)內(nèi)容，更多關(guān)于Go判斷二叉樹對(duì)稱的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
詳解用Go語(yǔ)言實(shí)現(xiàn)工廠模式(Golang經(jīng)典編程案例)
這篇文章主要介紹了詳解用Go語(yǔ)言實(shí)現(xiàn)工廠模式(Golang經(jīng)典編程案例),文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
go浮點(diǎn)數(shù)轉(zhuǎn)字符串保留小數(shù)點(diǎn)后N位的完美解決方法
這篇文章主要介紹了go浮點(diǎn)數(shù)轉(zhuǎn)字符串保留小數(shù)點(diǎn)后N位解決辦法,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-05-05
如何利用Go語(yǔ)言實(shí)現(xiàn)LRU?Cache
這篇文章主要介紹了如何利用Go語(yǔ)言實(shí)現(xiàn)LRU?Cache，LRU是Least?Recently?Used的縮寫，是一種操作系統(tǒng)中常用的頁(yè)面置換算法，下面我們一起進(jìn)入文章了解更多內(nèi)容吧,需要的朋友可以參考一下2022-03-03
go?mod?tidy報(bào)錯(cuò):zip:?not?a?valid?zip?file解決辦法
這篇文章主要給大家介紹了關(guān)于go?mod?tidy報(bào)錯(cuò):zip:?not?a?valid?zip?file的解決辦法,go mod是進(jìn)行代碼管理，這錯(cuò)誤是因?yàn)楸镜胤种Ш瓦h(yuǎn)程分支沖突,本文通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-01-01
在golang中字符串的拼接方式有多種,本文將會(huì)介紹比較常用的幾種方式,并且對(duì)各種方式進(jìn)行壓測(cè),具有一定的參考價(jià)值,感興趣的可以了解一下2024-01-01
橋接是一種結(jié)構(gòu)型設(shè)計(jì)模式，可將業(yè)務(wù)邏輯或一個(gè)大類拆分為不同的層次結(jié)構(gòu)，從而能獨(dú)立地進(jìn)行開發(fā)，本文將通過(guò)代碼示例詳細(xì)給大家介紹一下Golang橋接模式,需要的朋友可以參考下2023-06-06
在Golang中，異常處理是非常重要的一部分，能夠有效地控制和處理代碼中的異常情況。通過(guò)Golang的異常處理機(jī)制，可以優(yōu)雅地捕獲和處理異常，保障代碼的可靠性和穩(wěn)定性。同時(shí)，Golang還提供了豐富的工具和API，幫助開發(fā)者更加輕松地進(jìn)行異常處理2023-04-04
在搭建項(xiàng)目中一般都會(huì)有確定項(xiàng)目根目錄的絕對(duì)路徑的需求,下面這篇文章主要給大家介紹了關(guān)于Golang實(shí)踐指南之獲取目錄文件列表的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-01-01
Go語(yǔ)言定時(shí)任務(wù)cron的設(shè)計(jì)與使用
這篇文章主要為大家詳細(xì)介紹了Go語(yǔ)言中定時(shí)任務(wù)cron的設(shè)計(jì)與使用,文中的示例代碼講解詳細(xì),對(duì)我們深入掌握Go語(yǔ)言有一定的幫助,需要的可以參考下2023-11-11
隨著互聯(lián)網(wǎng)的快速發(fā)展和數(shù)據(jù)交換的廣泛應(yīng)用，各種數(shù)據(jù)格式的處理成為軟件開發(fā)中的關(guān)鍵問(wèn)題，本文將介紹?Golang?中?JSON?編碼與解碼的相關(guān)知識(shí)，幫助大家了解其基本原理和高效應(yīng)用，需要的可以收藏一下2023-05-05