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

この記事は約3分で読めます。

 

問題

原文

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:

Example 2:

Example 3:

 

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -104 <= Node.val <= 104

内容

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

 

解答2

 

 

補足・参考・感想

TreeNodeの構造

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

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

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

 

前:70. Climbing Stairs

次:101. Symmetric Tree

LeetCode 解答・解説記事一覧

コメント