문제

• tree 두개가 identical 한지 판별
• 위치와 value 모두 같아야 함

풀이

• dfs를 두개를 동시에

예외

• p = [1,2], q = [1,null,2]의 경우, 2 노드의 자리가 다르기 때문에 false
  => None도 자리 표시를 위해 노드로 인식해야함
• 둘 다 빈 경우도 같은 tree 임

from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        q1 = deque()
        q2 = deque()

        if p and q:
            q1.append(p)
            q2.append(q)
            while q1 and q2:
                thisNode1 = q1.popleft()
                thisNode2 = q2.popleft()
                if thisNode1 and thisNode2:
                    if thisNode1.val == thisNode2.val:
                        q1.append(thisNode1.left)
                        q1.append(thisNode1.right)
                        q2.append(thisNode2.left)
                        q2.append(thisNode2.right)
                    else:
                        # same location, but diff. value
                        return False
                elif not thisNode1 and not thisNode2:
                    # both are empty node
                    pass
                else:
                    # one of them is empty, and another is not
                    return False
            if not q1 and not q2:
                # if both Q empty and done
                return True
            else:
                # one of them has left value
                return False
        elif not p and not q:
            # both are same due to empty
            return True
        else:
            # one of them is empty, and another is not
            return False

다소 if 지옥....^^............

결과

recursion이 더 빨랐으려나....

recursion 코드

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        global ans
        ans = True
        recursion(p, q)
        return ans

def recursion(subOne, subTwo):
    global ans
    if subOne and subTwo and subOne.val == subTwo.val:
        recursion(subOne.left, subTwo.left)
        recursion(subOne.right, subTwo.right)
    elif not subOne and not subTwo:
        pass
    else:
        ans = False

오히려 더 느리넵,,,, ㅎ,,,