スポンサーリンク

【LeetCode】 872. Leaf-Similar Trees 解答・解説【Python】

スポンサーリンク
スポンサーリンク
この記事は約4分で読めます。

 

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

 

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

 

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

 

 

ポイント

    • BFS
    • DFS

 

 

詳細

 

問題

 

原文

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

 

Example 1:

Example 2:

 

Constraints:

  • The number of nodes in each tree will be in the range [1, 200].
  • Both of the given trees will have values in the range [0, 200].

 

 

内容(和訳)

二分木のすべての葉を、左から右の順番に考えると、それらの葉の値は葉値のシーケンスを形成します。
例えば、上記の与えられた木では、葉値のシーケンスは (6, 7, 4, 9, 8) です。

二つの二分木は、それらの葉値のシーケンスが同じである場合に、葉が類似していると見なされます。

与えられた二つの木(ヘッドノードがroot1とroot2)が葉が類似している場合にのみ、trueを返します。

 

 

※chatGPTによる翻訳

 

解答

 

解答1:Python, BFS

 

root1とroot2の葉ノードが一致した場合はTrue、不一致の場合はFalseを返す。

葉ノードは左から右に向かって並べる必要がある。

 

BFSでは、キューに入れるときは、キューの右側から、右の子ノード→左の子ノードの順に入れる。

キューから取り出すときは、キューの右側から取り出す

 

子ノードを右→左の順にキューに入れ、

子ノードを左→右の順にキューから取り出す。

 

このようにすると葉ノードを左から右に向かって取得することができる。

 

取り出したroot1とroot2の葉ノードが一致するかを判定している

 

 

 

 

 

 

終わりに

補足・参考・感想

 

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

 

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

 

 

他の問題もどうぞ

 

前:649. Dota2 Senate

 

次:1448. Count Good Nodes in Binary Tree

 

LeetCode 解答・解説記事一覧

 

コメント