Zi 字媒體
2017-07-25T20:27:27+00:00
二元樹是一個常見的數據結構，結構像是下列
在每一個節點會存三件東西，一個是節點本身的值，另外兩個是存指向左右節點的位置，舉例來說，在上面圖的根節點(最上面的點)，本身的值是1，分別有兩條線指向左右兩個節點，當然節點也有可能不存在。
在python上面，我們可以很簡單的實作節點出來，如下
？
1
2
3
4
5
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
這邊我們定義一個物件叫做TreeNode(樹節點)，每一個節點有三個屬性可以存，val、left以及right，有了節點物件後，我們就可以利用節點物件建構出一個二元樹魯。
但有了二元樹這個數據結構後，我們要如何有效率的搜尋整個樹的結構?
常見的有兩種搜尋方式，一個是深度優先搜尋，一個是廣度優先搜尋。
深度優先便是沿著一個分支往深處探索，然後慢慢探索完全部節點。
廣度搜尋便是對每一層進行尋找
這邊要分享的Leetcode題目便是深度搜尋的一個例子- 中序遍歷
題目如下
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
stack = [root]
res = []
while len(stack) > 0:
curr = stack.pop()
if not isinstance(curr, TreeNode):
res.append(curr)
continue
if curr.right is not None:
stack.append(curr.right)
stack.append(curr.val)
if curr.left is not None:
stack.append(curr.left)
return res
用同樣的思路可以來解決100題的判斷是否為同一顆樹，可以對兩棵樹進行節點搜尋，發現有節點有不同的值，回傳False，如果都一樣且兩棵樹的節點數一致則回傳True
？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if (p is None) and (q is None):
return True
if (p is None) or (q is None):
return False
if p.val != q.val:
return False
stack_p = [p]
stack_q = [q]
while (len(stack_p) > 0) and (len(stack_q) > 0):
curr_p = stack_p.pop()
curr_q = stack_q.pop()
if type(curr_p) != type(curr_q):
return False
if not isinstance(curr_p, TreeNode):
if curr_p != curr_q:
return False
continue
if curr_p.right is not None:
stack_p.append(curr_p.right)
if curr_q.right is not None:
stack_q.append(curr_q.right)
stack_p.append(curr_p.val)
stack_q.append(curr_q.val)
if curr_p.left is not None:
stack_p.append(curr_p.left)
if curr_q.left is not None:
stack_q.append(curr_q.left)
if len(stack_p) != len(stack_q):
return False
return True
寫了
5860316篇文章，獲得
23313次喜歡