二分木
二分木(binary tree)は、全ての節点において子が2個以下である木構造。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
二分木の走査
二分木の走査は、以下の4つの走査方法がある。
- 先行順： 節点、左部分木、右部分木の順に走査する。
- 中間順： 左部分木、節点、右部分木の順に走査する。
- 後行順： 左部分木、右部分木、節点の順に走査する。
- 幅優先探索： 木を1階層ずつ走査する。
先行順、中間順、後行順の違いは節点の走査順にあり、
節点を左右より先に走査するのは先行順、左右の中間で走査するのは中間順、左右より後に走査するのは後行順となる。
それぞれの操作方法を実現するには、回帰と反復のアルゴリズムがある。
回帰アルゴリズム
先行順
class Solution:
def preorder_traversal(self, root: Optional[TreeNode]) -> List[int]:
def preorder(node: Optional[TreeNode]):
# 再帰の終了条件 (leaf node)
if node is None:
return
# 節点の処理
ans.append(node.val)
# 左部分木の処理
preorder(node.left)
# 右部分木の処理
preorder(node.right)
ans = []
preorder(root)
return ans
中間順
class Solution:
def inorder_traversal(self, root: Optional[TreeNode]) -> List[int]:
def inorder(node: Optional[TreeNode]):
# 再帰の終了条件 (leaf node)
if node is None:
return
# 左部分木の処理
inorder(node.left)
# 節点の処理
ans.append(node.val)
# 右部分木の処理
inorder(node.right)
ans = []
inorder(root)
return ans
後行順
class Solution:
def postorder_traversal(self, root: Optional[TreeNode]) -> List[int]:
def postorder(node: Optional[TreeNode]):
# 再帰の終了条件 (leaf node)
if node is None:
return
# 左部分木の処理
postorder(node.left)
# 右部分木の処理
postorder(node.right)
# 節点の処理
ans.append(node.val)
ans = []
postorder(root)
return ans
反復アルゴリズム
先行順
class Solution:
def preorder_traversal(self, root: TreeNode) -> List[int]:
ans = []
if not root:
return ans
stack = [root]
while stack:
node = stack.pop()
# 節点の処理
ans.append(node.val)
if node.right:
# 右の子をスタックに追加
stack.append(node.right)
if node.left:
# 左の子をスタックに追加
stack.append(node.left)
return ans
中間順
class Solution:
def inorder_traversal(self, root: TreeNode) -> List[int]:
ans = []
if not root:
return ans
stack = []
node = root
while stack or node:
if node:
# 左部分木を最後までたどり、たどる順でstackに積む
stack.append(node)
node = node.left
else:
# 左部分木の最後までたどったら、stackから取り出してansに追加
node = stack.pop()
ans.append(node.val)
# 右部分木をたどる
node = node.right
return ans
後行順
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
ans = []
if not root:
return ans
stack = [root]
while stack:
node = stack.pop()
# 節点の処理
ans.append(node.val)
if node.left:
# 右の子をスタックに追加
stack.append(node.left)
if node.right:
# 左の子をスタックに追加
stack.append(node.right)
return ans[::-1]
幅優先探索
class Solution:
def level_order(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
if not root:
return ans
queue = [root]
while queue:
# 現在階層のノード数を取得
size = len(queue)
cur_level = []
for i in range(size):
node = queue.pop(0)
cur_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(cur_level)
return ans