LeetCode / Same Tree
https://leetcode.com/problems/same-tree/
Given two binary trees, 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.
LeetCodeではバイナリツリー(二分木)を使った問題が頻出しますが、そのうちの1つです。
2つのバイナリツリーが同一のものかどうか判定する問題です。
解答・解説
解法1
recursionを使った、スッキリしたコードは以下のようになります。
isSameTree(p,q)関数を「TreeNodeインスタンスのpとqが両方なければTrue、どちらか一方なければFalse、valが異なっていればFalse」と処理するものとして定義し、
最後にisSameTree(p.right,q.right)でTreeの右側が同一かの判定を、isSameTree(p.left,q.left)でTreeの左側が同一かの判定を行う再帰的な構造にします。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if not p and not q: return True if not q or not p: return False if p.val != q.val: return False return self.isSameTree(p.right, q.right) and self.isSameTree(p.left, q.left)
解法2
私は知らなかったのですが、pythonにはdequeというデータ型があるんですね。
こちらの記事が詳しいですが、
list型は先頭からデータを削除する際に要素の移動が発生するのでのオペレーションであるのに対し、deque型は先頭からも最後尾からもで要素を取り出し、削除することができるとのことです。
さて、このdeque型を使い、Iterationで解く公式の解法が以下の通りです。
from collections import deque class Solution: def isSameTree(self, p, q): def check(p, q): if not p and not q: return True if not q or not p: return False if p.val != q.val: return False return True deq = deque([(p, q),]) while deq: p, q = deq.popleft() if not check(p, q): return False if p: deq.append((p.left, q.left)) deq.append((p.right, q.right)) return True
list型でも似たようなコードになりますが、popleft関数はdequeならではの処理です。
check関数は、解法1で出てきた処理と全く同一です。
変数dequeに同一かどうかを判定するTreeNodeのペアを格納していき、check関数による判定をiterativeに行うという処理になります。