幅優先探索 (BFS) で二分木を右から見たときに見える節を並べる

木 (DFS と BFS)問題 92

二分木を右側から眺めたときに見える節の値を、上の段から順に返します。段ごとに読む幅優先探索で、各段のいちばん右の節を拾う練習です。

海外で定番の問題リスト 4 本には入っていません

問題

二分木の根 root を受け取ります。木を右側から眺めたときに見える節の値を、上の段から順に並べて返す関数を書いてください。

右から見えるのは、それぞれの段 (根からの深さが同じ節の集まり) でいちばん右にある節です
いちばん右の節は右の子とは限りません。その段に左の子しか無ければ、その左の子が見えます
各節は val (値)、left (左の子)、right (右の子) を持ちます。子が無いところは、Python では None、JavaScript では null、Go では nil です。Go の節は TreeNode で、Val、Left、Right と大文字で始まります
木が空のときは空の並び [] を返します
節の数は 0 以上 100 以下、値はどれも -100 以上 100 以下です

例では、木を上の段から左の順に読んだ値の並びで書きます。子が無いところは null です。

入力と出力の例

例 1

根が 8、その下が 4 と 12、4 の下に 2 と 6、12 の右に 14 があります。右から見ると、8、12、14 が見えます。

root = [8, 4, 12, 2, 6, null, 14]

[8, 12, 14]

例 2

いちばん下の段には、左側の 2 の下の 6 しかありません。右の子ではありませんが、その段でいちばん右なので見えます。

root = [1, 2, 3, 6]

[1, 3, 6]

例 3

空の木からは何も見えません。

root = []

[]

面接での聞かれ方

段ごとに読む幅優先探索の応用として、ミドルの面接でよく出ます。

「二分木を右から見たときに見える節を、上から順に返してください」
二分木を段ごとに読む問題 (この一覧の tree-levels) の続きとして出されることがよくあります
「深さ優先探索 (DFS) でも書けますか？」と聞かれることがあります。右の子を先にたどり、その深さに初めて来たときの節を拾えば同じ答えになります

ミドルの問題なので、「右の子だけをたどればよい」という早とちりをせず、例 2 のような形を自分で思いつけるかが見られます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。

再帰は、同じ形の小さい問題に分けて自分を呼ぶ書き方です。木の深さや、全部の組み合わせを数える問題で使います。

まず考える手順

段 1

まず思いつきやすいのは、根から右の子だけをたどる書き方です。これは例 2 で外れます。いちばん下の段の 6 は左側の枝にあり、右の子だけでは届きません。

段 2

右から見える節は、段ごとに 1 つ、その段のいちばん右の節です。そこで、木を段ごとに読みます。キューに今の段の節を入れておき、段の数だけ取り出しながら、その子を左、右の順にキューの後ろへ入れます。

段 3

左から右の順に取り出すので、その段で最後に取り出した節がいちばん右です。段を読み終えるたびに、最後の節の値を答えに足します。

段 4

木が空なら、1 段目に何も入れずに、空の並びを返します。

解答

Python

def right_side_view(root):
    out = []
    lv = [root] if root else []
    while lv:
        out.append(lv[-1].val)
        kids = []
        for n in lv:
            kids.append(n.left)
            kids.append(n.right)
        lv = [k for k in kids
              if k]
    return out

JavaScript

function rightSideView(root) {
  const out = [];
  if (root === null) {
    return out;
  }
  let level = [root];
  while (level.length > 0) {
    const next = [];
    for (const node of level) {
      if (node.left) {
        next.push(node.left);
      }
      if (node.right) {
        next.push(node.right);
      }
    }
    out.push(level.at(-1).val);
    level = next;
  }
  return out;
}

Go

func rightSideView(
	root *TreeNode,
) []int {
	out := []int{}
	if root == nil {
		return out
	}
	level := []*TreeNode{root}
	for len(level) > 0 {
		next := []*TreeNode{}
		for _, n := range level {
			if n.Left != nil {
				next = append(
					next, n.Left)
			}
			if n.Right != nil {
				next = append(
					next, n.Right)
			}
		}
		last := level[len(level)-1]
		out = append(out, last.Val)
		level = next
	}
	return out
}

キューの代わりに、今の段の節を左から順に並べた並びを持ち、段ごとに次の段の並びを作り直します。今の段の並びの最後の節が、その段のいちばん右です。

計算量

時間は O(n) です。どの節も 1 回キューに入り、1 回取り出されます
使う記憶は O(w) です。w はいちばん節の多い段の節の数で、キューに 1 段分が入ります。いちばん悪いと O(n) です

よくある間違い

右の子だけをたどる。例 2 の 6 のように、左側の枝にしか節が無い段で見落とします
段の区切りを付けずにキューを回す。取り出すたびに答えに足すと、全部の節が入ります。段の数を先に数えておき、その数だけ取り出したところで 1 段と見ます
子を右、左の順に入れて、最後の節を拾う。入れる順を逆にしたなら、拾うのは段の最初の節です。入れる順と拾う位置をそろえます
空の木で根の値を読む。例 3 のように root が空なら、何も読まずに空の並びを返します

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def right_side_view(root: TreeNode | None):
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # root の節は val、left、right を持ちます。空きは None です
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
# build_tree は、例と同じ並びから木を組みます
print(right_side_view(build_tree([8, 4, 12, 2, 6, None, 14])))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します