二分木（基礎）BFS, DFS | Coding InterviewCat | コーディング面接対策教材

二分木（基礎）BFS, DFS

LeetCode 練習問題集

問題	難易度	重要度	テクニック
Binary Tree Level Order Traversal	★★	高	Breadth First Search, BFS（幅優先探索）
Maximum Level Sum of a Binary Tree	★★★	高	Breadth First Search, BFS（幅優先探索）
Binary Tree Right Side View	★★★	中	Breadth First Search, BFS（幅優先探索）
Count Good Nodes in Binary Tree	★★★	高	Depth First Search, DFS（深さ優先探索）
Diameter of Binary Tree	★★★	高	Depth First Search, DFS（深さ優先探索）
Maximum Depth of Binary Tree	★★	高	Depth First Search, DFS（深さ優先探索）
Invert Binary Tree	★★	高	Depth First Search, DFS（深さ優先探索）
Balanced Binary Tree	★★	高	Depth First Search, DFS（深さ優先探索）
Same Tree	★★	高	Depth First Search, DFS（深さ優先探索）
Subtree of Another Tree	★★	高	Depth First Search, DFS（深さ優先探索）
Lowest Common Ancestor of a Binary Search Tree	★★★	高	Depth First Search, DFS（深さ優先探索）
Binary Tree Maximum Path Sum	★★★★	高	Depth First Search, DFS（深さ優先探索）

事前に必要な知識

配列、キュー、スタック

再帰関数

本章ではBreadth First Search, BFS（幅優先探索）、 Depth First Search, DFS（深さ優先探索）の2つの探索について説明します。先に探索(Search)とは何をすることかついて説明します。簡単にいうとグラフ上のノードとエッジを通りながらグラフの構造を把握していくことです。二分木の問題では一般的にノードのクラス（構造体）は以下のコードのように事前に定義されています。そして問題では基本的に根のノードしか与えられません。（...はEllipsisと呼ばれる省略を表すPythonの組み込み定数です。公式ドキュメントから参照できます。）


# ノードのクラス（構造体）
class Node:
    def __init__(self, val, left=None, right=None):
        # ノードの値
        self.val = val
        # 左の子ノード
        self.left = left
        # 右の子ノード
        self.right = right


# 基本的には根しか与えられない
def question(root: Node):
    ...

テック企業求人一覽

こちらの求人をrecoから紹介されたものです。 recoは現役の外資エンジニアがモックインタビュー付きで面接対策を行ってくれる転職サービスです。これらの企業にどのように準備に準備して振る舞えば採用されるのか的確なアドバイスを受ける事ができます。 InterviewCatの共著者のgaijineersさんが創業者として皆さんの転職をサポートします。