inorderとpreorderとpostorder
date: 2022-11-30 excerpt: inorderとpreorderとpostorderについて
tag: algorithmdata structureデータ構造bstbinary search tree二分木二分探索木
inorderとpreorderとpostorderについて
概要
- dfsの記録順序によって
inorderとpreorderとpostorderがある preorderは事前にスキャンNode -> Left -> Right
- (二分木の場合)
inorderはLeftをスキャンしてからRightをスキャンする順Left -> Node -> Right
postoderは戻りがけのスキャン- オイラー路(一筆書きの経路)を記録するときなど
- 二分探索木は一般的なデータの入れ方であれば、左に小さい値が入っているので、
inorderでデータを取得すれば昇順で結果を得られる
二分木の具体的な実装
ノード
class TreeNode:
def __init__(self, val: int, left: Optional["TreeNode"], right: Optional["TreeNode"]):
self.val = val
self.left = left
self.right = righ
preorder
def preorder_dfs(node, lst):
lst.append(node.val)
if node.left:
preorder_dfs(node.left, lst)
if node.right:
preorder_dfs(node.right, lst)
inorder
def inorder_dfs(node, lst):
if node.left:
inorder_dfs(node.left, lst)
lst.append(node.val)
if node.right:
inorder_dfs(node.right, lst)