給定一個二叉樹，如何判斷它是對稱的

給定一個二叉樹，檢查它是否是鏡像對稱的。

例如，二叉樹 [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

進階：

你可以運用遞歸和迭代兩種方法解決這個問題嗎？

解答：

一棵二叉樹對稱，則需要滿足：根的左右子樹是鏡像對稱的

也就是說，每棵樹的左子樹都和另外一顆樹的右子樹鏡像對稱，左子樹的根節(jié)點值與右子樹的根節(jié)點值相等

所以，我們需要比較：

• 左右子樹的根節(jié)點值是否相等
• 左右子樹是否鏡像對稱

邊界條件：

• 左右子樹都為 null 時，返回 true
• 左右子樹有一個 null 時，返回 false

解法一：遞歸

const isSymmetric = function(root) {
    if(!root) return true
    var isEqual = function(left, right) {
        if(!left && !right) return true
        if(!left || !right) return false
        return left.val === right.val
         && isEqual(left.left, right.right)
         && isEqual(left.right, right.left)
    }
    return isEqual(root.left, root.right)
};

復雜度分析：

• 時間復雜度：O(n)
• 空間復雜度：O(n)

解法二：迭代

利用棧來記錄比較的過程，實際上，遞歸就使用了調用棧，所以這里我們可以使用棧來模擬遞歸的過程

• 首先根的左右子樹入棧
• 將左右子樹出棧，比較兩個數(shù)是否互為鏡像
• 如果左右子樹的根節(jié)點值相等，則將左子樹的 left 、右子樹的 right 、左子樹的 right 、右子樹的 left 依次入棧
• 繼續(xù)出棧（一次出棧兩個進行比較）…….

依次循環(huán)出棧入棧，直到棧為空

const isSymmetric = function(root) {
    if(!root) return true
    let stack = [root.left, root.right]
    while(stack.length) {
        let right = stack.pop()
        let left = stack.pop()
        if(left && right) {
            if(left.val !== right.val) return false
            stack.push(left.left)
            stack.push(right.right)
            stack.push(left.right)
            stack.push(right.left)
        } else if(left || right) {
            return false
        }
    }
    return true
};

復雜度分析：

• 時間復雜度：O(n)
• 空間復雜度：O(n)