Zenn
😊

145. Binary Tree Postorder Traversal

に公開
PHP
TypeScript
LeetCode
tech

バイナリツリーの根ノードが与えられたとき、そのノードの値を「後順（ポストオーダー）」で巡回した結果を返してください。

例：

例 1:

入力： root = [1,null,2,3]

出力： [3,2,1]

説明：
後順巡回では「左 → 右 → 根」の順でノードを訪れます。

例 2:

入力： root = [1,2,3,4,5,null,8,null,null,6,7,9]

出力： [4,6,7,5,2,9,8,3,1]

説明：
同様に「左 → 右 → 根」の順でノードを巡回します。

例 3:

入力： root = []

出力： []

説明：
木が空なので、結果も空になります。

例 4:

入力： root = [1]

出力： [1]

説明：
ノードが1つだけの場合、そのノード自身が出力になります。

制約：

  • ノードの数は 0 から 100 の範囲です。
  • 各ノードの値は -100 から 100 の範囲です。

1. postorderTraversal($root)

  • 入力が null（空の木）なら空配列を返す。
  • 空でない場合は、$result 配列を作成し、helper 関数で値を詰める。

2. helper($node, &$result)

  • 再帰関数であり、以下の順に処理：
    • 左の子へ移動（$node->left）
    • 右の子へ移動（$node->right）
    • 現在のノードの値を $result に追加

Discussion