inorderとpreorderとpostorder

inorderとpreorderとpostorderについて

タグ binary search tree 二分探索木

概要

  • 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)

参考