LeetCode，Go 實現對稱二叉樹的判別
力扣題目：
給定一個二叉樹，檢查它是否是鏡像對稱的。
解題思路
我們先思考下，樹對稱的條件是什麼？
-
對於樹的左子樹，和右子樹，它們的根節點肯定是相同的
-
每個樹的左子樹必須與另一個樹的右子樹鏡像對稱
-
每個樹的右子樹必須與另一個樹的左子樹鏡像對稱
這樣就形成了遞歸問題，對於兩個子樹，需要判斷子樹的子樹是否對稱。注意臨界點：如果所給根節點，爲空，那麼是對稱。
程序實現
func isSymmetric(root *TreeNode) bool {
return isMirror(root, root)
}
func isMirror(t1 *TreeNode, t2 *TreeNode) bool {
if t1 == nil && t2 == nil {
return true
}
if t1 == nil || t2 == nil {
return false
}
return t1.Val == t2.Val && isMirror(t1.Left, t2.Right) && isMirror(t1.Right, t2.Left)
}複雜度分析
假設樹上一共有 n 個節點。
時間複雜度：題目中我們遍歷了這棵樹，所以漸進時間複雜度爲 O(n)。
空間複雜度：遞歸層數不超過 n，所以漸進空間複雜度爲 O(n)。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/rEtQpSzzW_ZZtfDkPbB_Qw