目標：
選取這題主要目的在於了解二元樹基本的延伸以外，
也介紹了另一個常用的資料結構：Queue,
用以處理迭代解(Iterative solution)的方法。

原題：

Question:
Given a binary tree, check whether it is a mirror of itself 
(ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:
    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

分析/解題：
題目給定一個二元樹，要求檢查是否為左右對稱(Symmetric)。
繼前一篇的樹的基本以後，今天同樣來談談另一個基本題，
幫助大家熟悉以外，也介紹一個資料結構Queue，
用來說明我們怎麼來解迭代解的。

這邊講的左右對稱是指從根節點將左右切開來看，左邊和右邊恰巧要對稱。
要解決這個問題並不困難，但要留意小細節。

首先，如果給定的根是NIL(null/None) =>
沒有東西仍然是可以達成左右對稱，所以必須回傳真值(true/True)。

扣掉這個狀況，再來觀察上面的圖可以發現，根節點毫不影響，
接著要比較的應該是左子樹跟右子樹是否對稱。
和前一題不同，以[1,2,2,3,4,4,3]為例，要符合對稱的條件，
應該要符合下面三點：

1. 左子樹根的值=右子樹根的值
2. 左子樹自己的左子樹(以本例是最左邊的3)要和右子樹自己的右子樹對稱
3. 左子樹的右子樹要和右子樹的左子樹對稱

請留意1的部分，
如果兩者均為NIL，表示下面不用比(空了)且兩者相等，
這時候應該回傳真值；而接下來再判斷其一為NIL的狀況，
表示兩者一定不相等(一個有節點一個是NIL)，這個技巧在上一篇同樣有使用到。
上面都沒成立的話，再判斷兩者值是否相等。
所以直觀上我們可以寫出這樣的遞迴模式：
(註:留意我們這樣寫只是用來表達整個演算的流程，
它通常並不能用來在某個語言執行，
這樣的用來表達概念的代碼叫作虛擬碼(pseudocode)，
虛擬碼通常不用嚴格按照特定規範，目的只是要先將你的流程想法釐清為主。)

isSym(root) {
  if root == NIL return true
  return isSymmetric(root.left, root.right)
}
isSymmetric(l, r) {
  if l == NIL and r == NIL return true
  if l == NIL or r == NIL return false
  if l.val != r.val return false
  return isSymmetric(l.left, r.right) and 
         isSymmetric(l.right, r.left)
}

寫成Java如下，注意我們這邊將isSymmetric函式的前2行合併了，
使用者也可以依自己習慣決定要不要這麼寫，速度上並不會有明顯差異。
同時，對Java而言，我們可以定義同名的函式，只要輸入的參數(parameter)型態或數量不同，JVM就可以知道哪一條式子是呼叫哪一個函式才正確。
這個做法稱為函式多載(Method Overloading)。

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetric(root.left, root.right);
    }
    public boolean isSymmetric(TreeNode l, TreeNode r) {
        if (l == null || r == null) return l == r;
        if (l.val != r.val) return false;
        return isSymmetric(l.left, r.right) && isSymmetric(l.right, r.left);
    }
}

Python並不支援函式多載，所以我們可以定義不同的名字來使用。
(註: 對於所有程式語言來說，
代表**"且"的操作，只要第一個條件為假**，後面就不會再進行判斷；
代表**"或"的操作，只要第一個條件為真**，後面也不會再進行判斷。
這個特性是為了節省時間，因為結果已經確定了。
讀者可以留意一下這點，
避免將一些希望一定要被執行的函式放在判斷條件的第二個以後，
以免發生預期要做的事情結果沒做的狀況。)

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        return self.isSym(root.left, root.right)
        
    def isSym(self, l: TreeNode, r: TreeNode) -> bool:
        if not l and not r: return True
        if not l or not r: return False
        return l.val == r.val and self.isSym(l.left, r.right) and self.isSym(l.right, r.left)

上面是遞迴的部分，接下來我們改成嘗試來使用迭代法解看看。
這邊首先要介紹一個資料結構Queue(隊列/佇列)。
隊列基本上就跟現場排隊名店一樣，扣除掉一些現實中的插隊之類的糟糕狀況外，
基本上是先排隊的可以先離開排隊序列而進場，
也就是說它的特性是先進先出(FIFO)。
我們將放一個東西到Queue中的操作叫作"Offer"(提供)，會放到隊列尾端；
從Queue裡面拿一個東西出來的操作叫作"Poll"(獲得)，會從隊列頭拿出。

這樣的特性對於解這題有什麼幫助呢？
我們可以如下操作：

1. 首先判斷root的部分，沒有問題的話拿出其左右(l跟r)，放到Queue裡面。
2. 此時Queue裡面有東西，一次拿兩個出來(poll兩次)，判斷l跟r本身
   (如同遞迴時一樣)
3. 接下來我們應該要判斷的是l.left, r.right跟l.right, r.left，
   所以我們將這四個節點依序offer至Queue中。
4. 重複2~3的動作直到Queue空掉或當中判斷為假的狀況即回傳假。
5. 如果Queue空掉了才離開循環，代表結果為真，回傳真值。

這裡我們利用了Queue的特性，只要依照我們目標的順序將東西放進Queue，
我們就可以一直按照正確的方式拿到2個需要被判斷的節點。
這邊要注意一點，如果兩個節點均為NIL，只代表這個部分往下沒有節點了，
不能直接回傳真值(因為其他部分還沒比較完)，
只是我們在這個位置不需要再放節點進到Queue中而已。

寫成虛擬碼如下：

isSymmetric(root) {
  create a queue named q
  if root == NIL return true
  q.offer(root.left)
  q.offer(root.right)
  while q is not empty {
    l = q.poll()
    r = q.poll()
    if l == NIL and r == NIL continue
    if l == NIL or r == NIL return false
    if l.val != r.val return false
    q.offer(l.left)
    q.offer(r.right)
    q.offer(l.right)
    q.offer(r.left)
  }
  return true
}

注意continue是用來表示這輪的迴圈不再繼續，直接跳到下一輪。

Java的LinkedList已經有實作包含Queue的資料結構了，
所以我們定義一個Queue時，實際上可以使用LinkedList作為宣告的物件。

Java:

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        if (root == null) return true;
        q.offer(root.left);
        q.offer(root.right);
        while (!q.isEmpty()) {
            TreeNode l = q.poll();
            TreeNode r = q.poll();
            if (l == null && r == null) continue;
            if (l == null || r == null) return false;
            if (l.val != r.val) return false;
            q.offer(l.left);
            q.offer(r.right);
            q.offer(l.right);
            q.offer(r.left);
        }
        return true;
    }
}

Python的部分，由於list的特性和Queue不太一致，
從開頭取出這點會讓用list模擬Queue的行為消耗大量的時間。
針對這點，Python有提供一個deque的物件可以使用，
取出請用popleft()，放入請用**append()**即可。
除了像Java這樣子的寫法以外，
我們也可以將其使用list的形式每兩個作為一個單位來操作，請參閱下面的程式碼。

Python:

from collections import deque
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        queue = deque([(root.left, root.right)])
        while queue:
            node1, node2 = queue.popleft()
            if not node1 and not node2:
                continue
            if node1 and node2 and node1.val == node2.val:
                queue.append((node1.left, node2.right))
                queue.append((node1.right, node2.left))
            else:
                return False
        return True

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(最糟的狀況均為O(N)，因為要查完所有資料有可能要塞完全部的node
遞迴的狀況如果該樹是平衡的話，空間複雜度可以降到O(logN))

「可以將左右比較的順序調過來嗎？」
(只要對應的節點是正確的，先比左邊還是先比右邊並無差異)

「如果我不想在前面單獨判斷root的話，有可能嗎？」
(去掉第4行，並將第一次offer的(root.left, root.right)改成(root, root)即可。)

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0136. Single Number (Easy)