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

はじめに
1. ポイント
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, BFS
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

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:

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8] Output: true

1
2

Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true

Example 2:

Input: root1 = [1,2,3], root2 = [1,3,2] Output: false

1
2

Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false

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

# 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 leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if root1 is None and root2 is None:
            return True
        elif root1 is None or root2 is None:
            return False
        elif self.BFS(root1) == self.BFS(root2):
            return True
        else:
            False



    def BFS(self, root):
        queue = deque()
        queue.append(root)
        leaves = []

        while queue:
            for i in range(len(queue)):
                node = queue.pop()
                if node.right is None and node.left is None: leaves.append(node.val)
                if node.right: queue.append(node.right)
                if node.left: queue.append(node.left)

        return leaves

# 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 leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:

if root1 is None and root2 is None:

return True

elif root1 is None or root2 is None:

return False

elif self.BFS(root1) == self.BFS(root2):

return True

else:

False

def BFS(self, root):

queue = deque()

queue.append(root)

leaves = []

while queue:

for i in range(len(queue)):

node = queue.pop()

if node.right is None and node.left is None: leaves.append(node.val)

if node.right: queue.append(node.right)

if node.left: queue.append(node.left)

return leaves

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

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

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

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

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

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

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

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

終わりに

補足・参考・感想

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

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

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

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

他の問題もどうぞ

前：649. Dota2 Senate

次：1448. Count Good Nodes in Binary Tree

LeetCode 解答・解説記事一覧