二元樹是一個常見的數據結構,結構像是下列
在每一個節點會存三件東西,一個是節點本身的值,另外兩個是存指向左右節點的位置,舉例來說,在上面圖的根節點(最上面的點),本身的值是1,分別有兩條線指向左右兩個節點,當然節點也有可能不存在。
在python上面,我們可以很簡單的實作節點出來,如下
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.
# 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
# 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