題目： 對(duì)稱(chēng)二叉樹(shù)
給定一個(gè)二叉樹(shù)寞奸，檢查它是否是鏡像對(duì)稱(chēng)的。
例如在跳，二叉樹(shù) [1,2,2,3,4,4,3] 是對(duì)稱(chēng)的枪萄。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面這個(gè) [1,2,2,null,3,null,3] 則不是鏡像對(duì)稱(chēng)的:
1
/ \
2 2
\ \
3 3
說(shuō)明：
如果你可以運(yùn)用遞歸和迭代兩種方法解決這個(gè)問(wèn)題，會(huì)很加分猫妙。
方案一：遞歸
如果一個(gè)樹(shù)的左子樹(shù)與右子樹(shù)鏡像對(duì)稱(chēng)瓷翻，那么這個(gè)樹(shù)是對(duì)稱(chēng)的。
因此割坠，該問(wèn)題可以轉(zhuǎn)化為：兩個(gè)樹(shù)在什么情況下互為鏡像齐帚？
如果同時(shí)滿(mǎn)足下面的條件，兩個(gè)樹(shù)互為鏡像：
- 它們的兩個(gè)根結(jié)點(diǎn)具有相同的值彼哼。
- 每個(gè)樹(shù)的右子樹(shù)都與另一個(gè)樹(shù)的左子樹(shù)鏡像對(duì)稱(chēng)对妄。
就像人站在鏡子前審視自己那樣。鏡中的反射與現(xiàn)實(shí)中的人具有相同的頭部敢朱，但反射的右臂對(duì)應(yīng)于人的左臂剪菱，反之亦然。
上面的解釋可以很自然地轉(zhuǎn)換為一個(gè)遞歸函數(shù)拴签，如下所示：
代碼一：
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func isSymmetric(_ root: TreeNode?) -> Bool {
if (root == nil) {return true}
return compereRoot(root?.left, root?.right)
}
func compereRoot(_ leftRoot: TreeNode?, _ rightRoot: TreeNode?) -> Bool {
if (leftRoot == nil){
return (rightRoot == nil)
}
guard rightRoot != nil else {
return false
}
guard (leftRoot?.val == rightRoot?.val) else {
return false
}
return compereRoot(leftRoot?.left, rightRoot?.right) && compereRoot(leftRoot?.right, rightRoot?.left)
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)孝常。因?yàn)槲覀儽闅v整個(gè)輸入樹(shù)一次，所以總的運(yùn)行時(shí)間為 O(n)蚓哩，其中 n 是樹(shù)中結(jié)點(diǎn)的總數(shù)构灸。
- 空間復(fù)雜度：遞歸調(diào)用的次數(shù)受樹(shù)的高度限制。在最糟糕的情況下岸梨，樹(shù)是線(xiàn)性的喜颁，其高度為 O(n)。因此盛嘿，在最糟糕的情況下洛巢，由棧上的遞歸調(diào)用造成的空間復(fù)雜度為 O(n)。
方案二：迭代
除了遞歸的方法外次兆，我們也可以利用隊(duì)列進(jìn)行迭代稿茉。隊(duì)列中每?jī)蓚€(gè)連續(xù)的結(jié)點(diǎn)應(yīng)該是相等的，而且它們的子樹(shù)互為鏡像。最初漓库，隊(duì)列中包含的是 root.left 以及 root.right恃慧。該算法的工作原理類(lèi)似于 BFS，但存在一些關(guān)鍵差異渺蒿。每次提取兩個(gè)結(jié)點(diǎn)并比較它們的值痢士。然后，將兩個(gè)結(jié)點(diǎn)的左右子結(jié)點(diǎn)按相反的順序插入隊(duì)列中茂装。當(dāng)隊(duì)列為空時(shí)怠蹂，或者我們檢測(cè)到樹(shù)不對(duì)稱(chēng)（即從隊(duì)列中取出兩個(gè)不相等的連續(xù)結(jié)點(diǎn)）時(shí)，該算法結(jié)束少态。
代碼二：
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func isSymmetric(_ root: TreeNode?) -> Bool {
if (root == nil) {return true}
var q = [TreeNode?]()
q.append(root?.left)
q.append(root?.right)
while !q.isEmpty {
let t1 = q.popLast()!
let t2 = q.popLast()!
//記得添加這個(gè)判斷城侧、、彼妻、不然變成死循環(huán)了
if (t1 == nil && t2 == nil) {
continue
}
if (t1?.val != t2?.val) {
return false
}
q.append(t1?.left)
q.append(t2?.right)
q.append(t1?.right)
q.append(t2?.left)
}
return true
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)嫌佑。因?yàn)槲覀儽闅v整個(gè)輸入樹(shù)一次，所以總的運(yùn)行時(shí)間為 O(n)侨歉，其中 n 是樹(shù)中結(jié)點(diǎn)的總數(shù)屋摇。
空間復(fù)雜度：搜索隊(duì)列需要額外的空間。在最糟糕的情況下幽邓，我們不得不向隊(duì)列中插入 O(n) 個(gè)結(jié)點(diǎn)炮温。因此，空間復(fù)雜度為O(n)颊艳。
