算法：對稱的二叉樹（LeetCode）

題目：請實現一個函數，用來判斷一棵二叉樹是不是對稱的。如果一棵二叉樹和它的鏡像一樣，那麼它是對稱的。

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。

1

/ \

2 2

/ \ / \

3 4 4 3

但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

1

/ \

2 2

\ \

3 3

示例 1：

輸入：root = [1,2,2,3,4,4,3]

輸出：true

示例 2：

輸入：root = [1,2,2,null,3,null,3]

輸出：false

限制：

0 <= 節點個數 <= 1000

解題思路：將二叉樹每一層都放到數組中獨自判斷，由左向右，為空則放空指針。

<code>/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root==nil{
        return true
    }
    tmp:=make([]*TreeNode,1)
    tmp[0]=root//根結點
    for len(tmp)>0{
        l:=len(tmp)
        for i:=0;i/<code>

執行用時 :4 ms, 在所有 Go 提交中擊敗了74.74%的用戶

內存消耗 :3 MB, 在所有 Go 提交中擊敗了100.00%的用戶

優化：使用遞歸，判斷左右子樹是否相等。

<code>/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root==nil{
        return true
    }
    return check(root.Left,root.Right)
}
func check(left,right *TreeNode) bool{
    if left==nil && right==nil{
        return true
    }
    if left==nil || right==nil || left.Val!=right.Val{
        return false
    }
//判斷左子樹的右子樹是否和右子樹的左子樹是否相等，判斷左子樹的左子樹和右子樹的右子樹是否相等。達到對稱。
    return check(left.Right,right.Left) && check(left.Left,right.Right)
}/<code>

執行用時 :4 ms, 在所有 Go 提交中擊敗了74.74%的用戶

內存消耗 :2.9 MB, 在所有 Go 提交中擊敗了100.00%的用戶

關鍵字: return 對稱 Right