Leetcode 100: Same Tree

 

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        return (p is None and q is None) or (p is not None and q is not None and p. val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right))

 

Idea

Recursion is easy to implement for this problem.

 

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        q1,q2 = deque([p]), deque([q])
        
        while stk1 and stk2:
            n1, n2 = q1.popleft(), q2.popleft()
            if (n1 is None and n2 is not None) or \
               (n1 is not None and n2 is None) or \
               (n1 and n2 and n1.val != n2.val):
                return False
                
            if n1 and n2:
                q1.append(n1.left)
                q2.append(n2.left)
                q1.append(n1.right)
                q2.append(n2.right)
            
        return True

 

Idea

Traverse two trees in same manner. Here I implement a bfs traverse.

Reference: https://discuss.leetcode.com/topic/7513/my-non-recursive-method (The author uses pre-order dfs)