[LeetCode] Python - 100. Same Tree

https://leetcode.com/problems/same-tree/

Same Tree - LeetCode

생각

트리가 같은지를 비교하려면 각각의 트리를 왼쪽의 서브트리, 오른쪽 서브트리가 동일한지를 판단하면 된다. 이를 재귀함수로 isSameTree(p의 왼쪽 서브트리, q의 왼쪽 서브트리) and isSameTree(p의 오른쪽 서브트리, q의 오른쪽 서브트리)로 판단할 수 있다.

 

이때 기저조건은 두가지가 있다.

첫번째, 양쪽의 노드가 null이 아닌데 값이 다른경우에는 False를 바로 리턴하면된다.

두번째, 양쪽의 노드가 null 일 경우는 null == null 이므로 True를 리턴한다.

 

Python Code

# 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: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q or p.val != q.val:
            return False
        if p.val == q.val:
            return (self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right))