バイナリツリー_プリオーダー走査 (Preorder Traversal)の実装　#441

今回はデータ構造の一種であるバイナリツリーにおいて、データを「プリオーダー走査」(Pre-order Traversal)する方法についてです。

バイナリツリー自体の概要は以下にまとめました。

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

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

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

プリオーダー走査とは

プリオーダー走査は次の順序で各ノードを訪問します。

1. ルート訪問: 最初に、ツリーのルートノードを訪問します。

2. 左サブツリーの走査: 次に、ルートの左側にあるサブツリーをプリオーダー走査の順序で巡ります。

3. 右サブツリーの走査: 左サブツリーの走査が完了したら、右側にあるサブツリーを同じくプリオーダー走査で巡ります。

このプロセスは、各サブツリーに対して再帰的に繰り返されます。

具体的なコード例

Pythonでプリオーダー走査をするコードを書いてみました。
渡していく左や右の値 (root) がNoneになるまで、再帰的な処理が続くようにしています。

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

もっといい書き方がある気がしますがとりあえず。

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