Same tree#

Levels: level-2

Data structures: tree

Algorithms: dfs

Practice Link#

LeetCode

Description#

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.

Examples#

text

1Input:     1         1
2          / \       / \
3         2   3     2   3
4
5        [1,2,3],   [1,2,3]
6
7Output: true

text

1Input:     1         1
2          /           \
3         2             2
4
5        [1,2],     [1,null,2]
6
7Output: false

Python Solution#

 1from collections import deque
 2
 3
 4class TreeNode(object):
 5    def __init__(self, x):
 6        self.val = x
 7        self.left = None
 8        self.right = None
 9
10
11class Solution:
12    # Recursive solution
13    def isSameTree(self, p, q):
14        """
15        :type p: TreeNode
16        :type q: TreeNode
17        :rtype: bool
18        """
19        # p and q are both None
20        if not p and not q:
21            return True
22        # one of p and q is None
23        if not q or not p:
24            return False
25        if p.val != q.val:
26            return False
27        return self.isSameTree(p.right, q.right) and \
28               self.isSameTree(p.left, q.left)
29
30    # Iterative solution
31    def isSameTreeIterative(self, p, q):
32        """
33        :type p: TreeNode
34        :type q: TreeNode
35        :rtype: bool
36        """
37        def check(p, q):
38            # if both are None
39            if not p and not q:
40                return True
41            # one of p and q is None
42            if not q or not p:
43                return False
44            if p.val != q.val:
45                return False
46            return True
47
48        deq = deque([
49            (p, q),
50        ])
51        while deq:
52            p, q = deq.popleft()
53            if not check(p, q):
54                return False
55
56            if p:
57                deq.append((p.left, q.left))
58                deq.append((p.right, q.right))
59
60        return True