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型は先頭からデータを削除する際に要素の移動が発生するので$O(n)$のオペレーションであるのに対し、deque型は先頭からも最後尾からも$O(1)$で要素を取り出し、削除することができるとのことです。
さて、この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に行うという処理になります。