【LeetCode】 100. Same Tree 解答・解説【Python】

問題
1. 原文
2. 内容
方針
解答
1. 解答1
2. 解答2
補足・参考・感想

問題

原文

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3] Output: true

1
2

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2] Output: false

1
2

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2] Output: false

1
2

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

The number of nodes in both trees is in the range [0, 100].

-10⁴ <= Node.val <= 10⁴

内容

2つの二分木p,qが与えられます。p,qが同じか判定する関数を書いてください。

2つの二分木は、同じ構造であり、同じ値のノードを持つ時に同じと考えられます。

制約

・p,qのノードの数は0~100

・ノードの値は-10^4 ~ 10^4

※正しくない可能性があります。

方針

➀再帰的に解く

p,qがどちらもNone(空)ならTrue

p,qのいずれかがNoneならFalse

上記2パターン以外でp,qの親ノードの値が不一致ならFalse

上記3パターンの判定を関数にし、Falseでなければp,qの左右のノード同士で再度関数を呼び出す

②stackを使う

stackにp,qの木を入れてスタートし、stackに値がある間は以下を繰り返す

・p,qの親ノードが一致するか判定

・一致していればstackにp,qの左右それぞれの子ノードをタプルで入れる

stackがなくなるまでFalseがでなければ最後にTrueを返す

解答

解答1

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        #p,qが共にない場合
        if p is None and q is None:
            #Trueを返す
            return True
        #p,qのいずれかがないNone(他言語で言うnullオブジェクト？)だった場合
        if p is None or q is None:
            #Falseを返す
            return False
        #p,qの親ノードが不一致なら
        if p.val != q.val:
            #Falseを返す
            return False
        #p,qの左側の子ノードと右側の子ノードで同じことを再帰的に繰り返す
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

class Solution:

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:

#p,qが共にない場合

if p is None and q is None:

#Trueを返す

return True

#p,qのいずれかがないNone(他言語で言うnullオブジェクト？)だった場合

if p is None or q is None:

#Falseを返す

return False

#p,qの親ノードが不一致なら

if p.val != q.val:

#Falseを返す

return False

#p,qの左側の子ノードと右側の子ノードで同じことを再帰的に繰り返す

return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

解答2

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        #stackにp,qをタプルで入れる
        stack = [(p,q)]
        #stackに値がある限りループ
        while stack:
            #n,mにstackの一番上の値を入れる
            n,m = stack.pop()
            #n,mに値がある場合
            if n and m:
                #n.valとm.valが不一致の場合
                if n.val != m.val:
                    #Falseを返す
                    return False
                #stackにn,mの左右の子ノードをタプルで入れる
                stack.append((n.right, m.right))
                stack.append((n.left, m.left))
            #nとmが違うオブジェクトの場合
            elif n is not m:
                #Falseを返す
                return False
        #ここまでで不一致のノードはなかったのでTrueを返す
        return True

class Solution:

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:

#stackにp,qをタプルで入れる

stack = [(p,q)]

#stackに値がある限りループ

while stack:

#n,mにstackの一番上の値を入れる

n,m = stack.pop()

#n,mに値がある場合

if n and m:

#n.valとm.valが不一致の場合

if n.val != m.val:

#Falseを返す

return False

#stackにn,mの左右の子ノードをタプルで入れる

stack.append((n.right, m.right))

stack.append((n.left, m.left))

#nとmが違うオブジェクトの場合

elif n is not m:

#Falseを返す

return False

#ここまでで不一致のノードはなかったのでTrueを返す

return True

補足・参考・感想

TreeNodeの構造

# 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

# 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

解答欄の上の方に↑こんなコードがあります。これはp,qの構造をクラスで示しています。

self.valが二分木p,qの親ノード、self.leftが二分木p,qの左側の子ノード、self.rightが二分木p,qの右側の子ノードです。

左右のノードはそれ自体が二分木であり、それらが連なって階層的な二分木を構成していることがあります。

前：70. Climbing Stairs

次：101. Symmetric Tree

LeetCode 解答・解説記事一覧