二元樹是一個常見的數據結構,結構像是下列
在每一個節點會存三件東西,一個是節點本身的值,另外兩個是存指向左右節點的位置,舉例來說,在上面圖的根節點(最上面的點),本身的值是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
|