iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 15
1
Software Development

從LeetCode學演算法系列 第 15

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

目標:
選取這題主要目的在於了解二元樹基本的延伸以外,
也介紹了另一個常用的資料結構: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.rightl.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)


上一篇
[Day 14] 從LeetCode學演算法 - 0100. Same Tree (Easy)
下一篇
[Day 16] 從LeetCode學演算法 - 0136. Single Number (Easy)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言