두 트리 비교하기

한국 코테에서는 트리가 잘 안 나오는 것 같다

자료구조 때 했었는데 직접 구현해본 기억이 별로 없는 듯

100. Same Tree

두 트리가 같으면 True, 다르면 False를 반환하는 문제다

처음에는 inorder 등 순회를 하면서 가지고 온 결과가 같으면 같은 트리지~ 생각하고 풀었는데 막상 확인해 보니

결과 배열에 들어있는 노드들의 값은 같았지만 구조가 다른 경우 (null) 등.. 정확하게 파악되지 않았다

다른 트리임에도 res 배열 값이 같아서 같은 트리로 취급됨

주석처리한 부분이 문제의 코드이고

# 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:
        # def inorder(curr, res):
        #     if curr !=None:
        #         inorder(curr.left, res)
        #         res.append(curr.val)
        #         inorder(curr.right, res)

        
        # resp, resq =[] , []
        # inorder(p, resp)
        # inorder(q, resq)

        # if resp==resq:
        #     return True
        # else:
        #     return False

        def sameTree(a, b):
            if not a and not b:
                return True
            if not a or not b:
                return False
            if a.val!= b.val:
                return False
            return sameTree(a.right, b.right) and sameTree(a.left, b.left)

        return sameTree(p, q)

 

sameTree func를 recursive하게 호출해서 , 끝에 닿았을 때 둘 다 없다면 같이 끝난 거니까 True

둘 중 하나만 없다면 False, Elif val isnt same, return True.

For the last line, by the && operator, if two return values are all True, then return True.

Else False.