📌

LeetCode 94. binary-tree-inorder-traversal - 再帰とスタックの2つのアプローチ

に公開
LeetCode
tech

94. binary-tree-inorder-traversal

Difficulty: Easy

https://leetcode.com/problems/binary-tree-inorder-traversal

アプローチ

解き方が全然わからない。。。
とりあえずprintしてデータ構造を確認し、テストコードを通すことを考える。

pp root
#<TreeNode:0x00007fb3d79d5570
 @left=nil,
 @right=
  #<TreeNode:0x00007fb3d79d5368
   @left=#<TreeNode:0x00007fb3d79d5200 @left=nil, @right=nil, @val=3>,
   @right=nil,
   @val=2>,
 @val=1>
#<TreeNode:0x00007fb3d79d5368
 @left=#<TreeNode:0x00007fb3d79d5200 @left=nil, @right=nil, @val=3>,
 @right=nil,
 @val=2>
#<TreeNode:0x00007fb3d79d5200 @left=nil, @right=nil, @val=3>

アプローチ1: 再帰

再帰的にメソッドを呼び出すのが良さそうだが、再帰関数に変数をどう渡してけばいいか。関数1つのみだと変数の受け渡しができない。

  • 戻り値用の変数を定義するメイン関数
  • 変数が渡されてleftノードとrightノードを再帰するヘルパー関数
    の2つを定義することで解決する。

ruby

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {Integer[]}
def inorder_traversal(root)
    results = []
    _inorder_traversal(root,results)
    return results
end

def _inorder_traversal(root, results)
    if !root.nil?
      _inorder_traversal(root.left, results)
      results << root.val
      _inorder_traversal(root.right, results)
    end
    return results
end

アプローチ2: スタック

LeetCodeの中で紹介されていたスタックを使った方法。

  • スタック: データの追加（プッシュ）と削除（ポップ）が後入れ先出し（LIFO: Last-In, First-Out）の原則に従うデータ構造

ruby

def inorder_traversal(root)
    stacks = []
    results = []
    current = root
    while(current || !stacks.empty?)
      while(current)
        stacks.push(current)
        current = current.left
      end
      current = stacks.pop
      results.push(current.val)
      current = current.right
    end
    return results
end

python

rubyからの修正点

  • whileループの書き方を修正
  • list型のpushからappendへ変更
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = []
        results = []
        current = root

        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            results.append(current.val)
            current = current.right
        return results

typescript

  • 型定義を追加
function inorderTraversal(root: TreeNode | null): number[] {
  let results: number[] = []
  let stack: (TreeNode | null)[] = []
  let current: TreeNode | null = root

  while(current !== null|| stack.length !== 0){
    while(current !== null){
      stack.push(current)
      current = current.left
    }
    current = stack.pop()
    results.push(current.val)
    current = current.right
  }
  return results
};

golang

  • whileループをforループに変更
  • リストや配列に直接push/popすることはできないため、スライスを使って実装する
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    var results []int
    var stack []*TreeNode
    current := root

    for current!= nil || len(stack) != 0 {
        for current !=nil {
            stack = append(stack, current)
            current = current.Left
        }
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        results = append(results, current.Val)
        current = current.Right
    }
    return results
}

// スタックから要素を取り出す（pop）
current = stack[len(stack)-1]     // 末尾の要素を取得
stack = stack[:len(stack)-1]      // 末尾の要素を削除

学びのポイント

  • tree構造をinorderで操作する再帰とスタックの2つの手順を実装した
    • 「inorder」とは、二分木（binary tree）の中順探索（inorder traversal）というアルゴリズム
      • Inorder（中順探索）: 左の子 → 親ノード → 右の子
    • 中順探索の他にも、主に以下の2つの探索方法がある。
      • Preorder（前順探索）: 親ノード → 左の子 → 右の子
      • Postorder（後順探索）: 左の子 → 右の子 → 親ノード

Discussion