バイナリツリー_ポストオーダー走査(　Postorder Traversal)の実装　#443

バイナリツリーの走査方法の第3弾です。
バイナリツリーについて別で3本記事を書いています。

走査とは先頭から順にデータを見ていくことを指し、バイナリツリーを走査するアルゴリズムは主に４つあります。

Pre-order Traversal
In-order Traversal
Post-order Traversal
Level-order Traversal

このうちのPost-order Traversalについてです。

ポストオーダー走査とは

ポストオーダー走査は、バイナリツリーを巡る方法の一つで、ノードを「左→右→ルート」の順序で訪問します。この走査方法は、例えばバイナリツリーの削除機能において、ノードを削除した際にその子ノードまで削除したい場面で役に立ちます。

1. 左サブツリーを走査する

2. 右サブツリーを走査する

3. 右に移動できなかったらルートノードを訪問してデータ出力

ブログに分かりやすい図がありました。

うさぎでもわかる2分探索木

具体的なコード例

探索結果をresultに格納していき、最後に出力するようにしています。
まず自分で以下のように書いてみました。

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        def _preorder(root, result):
            if root:
                _preorder(root.left, result)
                _preorder(root.right, result)
                result.append(root.val)
            return result
        return _preorder(root, result)

前回のインオーダー走査との違いは、result.appendの位置だけです。
↓インオーダー走査のコード例

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        def _inorder(root, result):
            if root:
                _inorder(root.left, result)
                result.append(root.val)
                _inorder(root.right, result)
            return result
        
        return _inorder(root, result)

ここまでお読みいただきありがとうございました！

参考

うさぎでもわかる2分探索木　後編　2分探索木における4つの走査方法