DAY 15
1
Software Development

## [Day 15] 從LeetCode學演算法 - 0101. Symmetric Tree (Easy)

``````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.
``````

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

(註:留意我們這樣寫只是用來表達整個演算的流程，

``````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:

``````/**
* 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)

``````

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

Java:

``````class Solution {
public boolean isSymmetric(TreeNode root) {
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不太一致，

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

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

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

0136. Single Number (Easy)