Title

給定一個(gè)二叉樹(shù)，檢查它是否是鏡像對(duì)稱的。

例如，二叉樹(shù) [1,2,2,3,4,4,3] 是對(duì)稱的。

1/ \2 2/ \ / \ 3 4 4 3

但是下面這個(gè) [1,2,2,null,3,null,3] 則不是鏡像對(duì)稱的:

1/ \2 2\ \3 3

Solve

遞歸：深度優(yōu)先

如果一個(gè)樹(shù)的左子樹(shù)與右子樹(shù)鏡像對(duì)稱，那么這個(gè)樹(shù)是對(duì)稱的。

所以此問(wèn)題可以轉(zhuǎn)化為：兩棵樹(shù)在什么情況下互為鏡像？必須滿足以下條件：

它們的兩個(gè)根節(jié)點(diǎn)具有相同的值

每個(gè)樹(shù)的右子樹(shù)與另一個(gè)樹(shù)的左子樹(shù)鏡像對(duì)稱

可以實(shí)現(xiàn)一個(gè)遞歸函數(shù)，通過(guò)「同步移動(dòng)」兩個(gè)指針的方法來(lái)遍歷這棵樹(shù)，p 指針和 q 指針一開(kāi)始都指向這棵樹(shù)的根，隨后 p 右移時(shí)，q 左移，p 左移時(shí)，q 右移。每次檢查當(dāng)前 p 和 q 節(jié)點(diǎn)的值是否相等，如果相等再判斷左右子樹(shù)是否對(duì)稱。

def isSymmetric_D(self, root: TreeNode) -> bool:def check(p: TreeNode, q: TreeNode):if p is None and q is None:return Trueif p is None or q is None:return Falsereturn p.val == q.val and check(p.left, q.right) and check(p.right, q.left)return check(root, root)

復(fù)雜度分析

假設(shè)樹(shù)上一共 n 個(gè)節(jié)點(diǎn)。

時(shí)間復(fù)雜度：這里遍歷了這棵樹(shù)，漸進(jìn)時(shí)間復(fù)雜度為 O(n)。

空間復(fù)雜度：這里的空間復(fù)雜度和遞歸使用的?？臻g有關(guān)，這里遞歸層數(shù)不超過(guò) n，故漸進(jìn)空間復(fù)雜度為 O(n)。

迭代：廣度優(yōu)先

引入一個(gè)隊(duì)列，初始化時(shí)把根節(jié)點(diǎn)入隊(duì)兩次，每次提取兩個(gè)節(jié)點(diǎn)并比較它們的值，隊(duì)列中每?jī)蓚€(gè)連續(xù)的節(jié)點(diǎn)英愛(ài)是相等的，而且它們的子樹(shù)互為鏡像，然后將兩個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)按相反的順序插入隊(duì)列中，當(dāng)隊(duì)列為空時(shí)，或者我們檢測(cè)到樹(shù)不對(duì)稱時(shí)，算法結(jié)束。

def isSymmetric_B(self, root: TreeNode) -> bool:def check(x: TreeNode, y: TreeNode):from queue import Queueq = Queue()q.put(x)q.put(y)while not q.empty():u = q.get()v = q.get()if not u and not v:continueif (not u or not v) or (u.val != v.val):return Falseq.put(u.left)q.put(v.right)q.put(u.right)q.put(v.left)return Truereturn check(root, root)

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n)，這里遍歷了這棵樹(shù)，漸進(jìn)時(shí)間復(fù)雜度為 O(n)。

空間復(fù)雜度：這里需要用一個(gè)隊(duì)列來(lái)維護(hù)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)最多進(jìn)隊(duì)一次，出隊(duì)一次，隊(duì)列中最多不會(huì)超過(guò) n 個(gè)點(diǎn)，故漸進(jìn)空間復(fù)雜度為 O(n)。

總結(jié)

以上是生活随笔為你收集整理的LeetCode Algorithm 101. Symmetric Tree的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。