iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 14
1
Software Development

從LeetCode學演算法系列 第 14

[Day 14] 從LeetCode學演算法 - 0100. Same Tree (Easy)

目標:
這題主要目的在於介紹常見的資料結構:樹(Tree)

原題:

Question:
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input:     1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
Output: true
Example 2:
Input:     1         1
          /           \
         2             2
        [1,2],     [1,null,2]
Output: false
Example 3:
Input:     1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
Output: false

分析/解題:
給定兩個二元樹,試寫出一個函式來檢查二者是否相等。
(相等的定義是指樹的結構相同,且其相同位置節點的值也相等)

到了第13篇,終於來到樹的部分了,
想當年大學時在演算法的課上被各種資料結構搞得眼花撩亂,
當中二元樹/二元搜尋樹真的只能算小兒科XD
(不信?有心更進階的讀者可以試試看了解一下紅黑樹)

扯遠了,我們回頭來談樹。
在程式的領域中,樹是指資料之間以一種長得像樹的方式連結在一起的資料結構(廢話XD),以外型而言就像樹狀圖族譜那樣子,
不過它們有一點比較特別,那就是他們的根通常是畫在上方,下面才是支幹。
如下圖我們所看到的:

  1. 每個圈圈我們稱之為節點(node)
  2. 最上面的節點是整棵樹的起始,所以我們就稱之為根(root)
  3. 就如族譜一樣,上面節點是下面直接連接的父母,
    所以我們稱如A是B和C的父節點(parent)(不要問我為什麼不叫母節點XD),
    B和C是A的子節點(child),同時B和C是兄弟節點(siblings)
  4. 任何從自身追尋血脈上去可以到達的節點均為你的祖先(ancestor)
    比如A是所有人的祖先,而B不是G的祖先。

From Wikipedia: Tree
From Wikipedia: Tree

樹本身並沒有規定一個節點要連接多少個節點或總共有多少個節點,
你可以子孫滿堂開枝散葉,也可以孑然一身孤苦伶仃,
只要有一個根在,就可以被稱做一棵樹。

不過這邊要介紹的是二元樹(binary tree),就有比較明確的限制了,
每個節點最多只能有2個分支。且左右分支是視作不同的,
將它們互相交換的話,前後兩個二元樹會被視為不同的二元樹。
由於只有2個分支,所以一個節點的兩個子節點又可以分別被叫做
左節點和右節點(left/right node),
單就這兩個節點來看,都可以各自視為一個二元樹,
同樣依照左右被稱作左子樹/右子樹(left/right subtree)
後續還有一個規範更嚴格,也更常被用到的二元樹稱為二元搜尋樹(Binary Search Tree, BST),這個我們之後會專門再開一篇講解。
上面這些均為樹的相當基本的部分,並不困難,還請詳加閱讀後再往下。

如同先前提過的linked list一樣,
當一個節點它有一邊沒有連接,或者是已經沒有子節點的時候,
嚴謹的資料結構會將其連接至NIL(表示什麼都沒有),
而在Java中用null,Python則用None表示。
一個Binary Tree, 15的左邊/17, 23, 25的左右其實都是NIL(恩,其實它也是BST)
一個Binary Tree, 15的左邊/17, 23, 25的左右其實都是NIL(恩,其實它也是BST)

回到問題,其實問題的輸入是透過array或list的型式,
但這邊LeetCode應該已經妥善處理好建造二元樹的過程了,我們暫且不管它。
我們如何判斷兩個二元樹是否相等呢?
由於相等的前提是結構相同且所有對應的節點的值也相同,
我們勢必要一個一個檢查才能知道結果,
所以我們必須要走訪整棵樹(Tree Traversal)。

一個標準的走訪分成四種模式:
前序、中序、後序以及層序(Pre-order/In-order/Post-order/Level-order)
我們這次只會先從最直覺的前序遍歷開始。

假設如題目所提,我們有兩棵二元樹,他們的root分別是p跟q,
那麼檢查它們是否相等的話,我們要做的事情是:

  1. 檢查pq是否相等
  2. 檢查p的左子樹q的左子樹是否相等
  3. 檢查p的右子樹q的右子樹是否相等
    唯有這三項均成立,我們才能說p跟q兩棵二元樹相等,否則即為不相等。
    接下來,我們先考慮2和3的部分,
    其實就等同於反複拿更小的子樹去做1~3的動作,
    直到比對的兩邊當中有不同或空掉的狀況。

我們拿下面的圖為例,可以簡單推論出,
當檢查兩個節點是否相等的狀況有幾個可確定:
a. 一邊有節點,另一邊沒有節點 => 結構已經不一樣了,所以兩棵樹不同
b. 兩邊均無節點 => 結構相同且沒有子節點,所以這個位置的子樹相同
c. 兩邊都有結點 => 檢查值是否相同,相同的話,再檢查左右子樹
(也就是回到上一段那邊的2~3)

所以,我們可以用連續呼叫自己這個解題函式的方式來解決這個問題,
其演算方式可以大致列成這樣:

isSameTree(p, q) {
    若p和q均為NIL,回傳真
    若p或q為NIL,回傳假(因為表示恰有一個是NIL)
    回傳 (p.val==q.val) 且 isSameTree(p.left, q.left) 且 isSameTree(p.right, q.right)
}

注意這樣子的比較,我們每次是先比較根節點
再比較左節點的部分,最後才是比較右節點
同時,每次呼叫isSameTree時,會一路往左邊先找下去,
直到左子樹找完了才會走訪右子樹的部分,所以順序是根-左-右
也就是一般所謂的前序遍歷(Pre-order Traversal)。

這種不斷呼叫自己來求解的方式,我們稱之為遞迴(Recursion,或譯遞歸)
這樣的解法一般稱為遞迴解(Recursive solution)

一般來說還會有另一種解法,
主要是透過額外的資料結構及迴圈,來解決問題,
這種方式叫做迭代法/迭代解(Iterative method/Iterative solution)
比較熟練的讀者若有興趣,可以自行嘗試使用Queue或Deque來解本題看看。

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 isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return ((p.val == q.val) && (isSameTree(p.left, q.left)) && (isSameTree(p.right, q.right)));
    }
}

Python的部分,由於NIL是用None來表示,
所以檢查可以用if not的方法來處理,且not運算的優先層級高於and/or
所以我們不用額外幫它加括號。

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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q: return True
        if not p or not q: return False
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

面試實際可能會遇到的問題:
「時間複雜度/空間複雜度?」
(如果答案為真的話,那麼每個節點均會走訪一次,故為O(N))
(空間複雜度的話,遞迴同樣會佔用記憶體空間,層數則取決於樹的層數,
如果是平衡樹(balanced tree)的話,因為分布要平衡(填滿),
每層的節點數量會是1, 2, 4, 8, 16, ..., 總和N=2的n次方-1,n為層數。
所以空間複雜度會是O(logN),N為節點的總數。
最差的狀況下,節點全部連在同一邊,那空間複雜度可以達到O(N)。)

「可以不用遞迴解嗎?」
(可以,有興趣的讀者可以嘗試看看,具體方式是使用Queue或Deque,
先將兩個根節點放入,接著每次取出一組節點對;
先比較節點,再將兩樹其左右node成對地放入裡面
重複迴圈,直到有不相等的狀況產生,或直到Queue/Deque內再無節點。)

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

下篇預告:
0101. Symmetric Tree (Easy)


上一篇
[Day 13] 從LeetCode學演算法 - 0092. Reverse Linked List II (Medium)
下一篇
[Day 15] 從LeetCode學演算法 - 0101. Symmetric Tree (Easy)
系列文
從LeetCode學演算法30

1 則留言

0
t19960804
iT邦新手 5 級 ‧ 2020-09-21 13:40:35

我想請問一下
這題的演算法當中我們為了確認子樹的node是不是遍歷完了
會有這一段"若p和q均為NIL,回傳真"
這樣子不就會變成說我們除了看得見的node要確認
最後一個子node還要繼續確認左右都是nil的node
這樣子時間複雜度是不是就為O(2^n)了?

Desolve iT邦新手 5 級 ‧ 2020-09-21 13:47:40 檢舉

不會啊,就最差的狀況而言,每一個node的左右都要確認是否為NIL,
總共有N個node,所以你要檢查最多2 * N次,而非2^N次。

我要留言

立即登入留言