Leetcode Python - 100. Same Tree

Leetcode #100 - Same Tree

이제 blind 75 leetcode를 풀어보겠습니다. https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions

리트코드의 문제 100 ‘Same Tree’을 파이썬으로 풀어 보도록 하겠습니다.

discuss 참고 포인트는 stack 을 이용한 pre-order traversal 을 이용하는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        stack = [(p, q)]
        
        while stack:
            n1, n2 = stack.pop()
            
            if n1 and n2 and n1.val == n2.val:
                stack.append((n1.left, n2.left))
                stack.append((n1.right, n2.right))
            elif not n1 and not n2:
                continue
            else:
                return False
            
        return True

시간복잡도는

• O(n) : 한번씩 방문

공간복잡도는

• O(h) : h는 깊이