100. Same Tree

문제)

100. Same Tree

 

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

 

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

 

Constraints:

• The number of nodes in both trees is in the range [0, 100].
• -104 <= Node.val <= 104

 

솔루션1)

- preorder 순회

- 순회 시 depth와  left/right 정보를 함께 저장해서 비교. 동일하면 same tree

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        DIR_NONE = 0
        DIR_LEFT = 1
        DIR_RIGHT = 2
        def recur(node, depth, direction, vals):
            if node is None:
                return
            
            vals.append([node.val, depth, direction])
            recur(node.left, depth + 1, DIR_LEFT, vals)
            recur(node.right, depth + 1, DIR_RIGHT, vals)
        
        a, b = [], []
        recur(p, 0, DIR_NONE, a)
        recur(q, 0, DIR_NONE, b)
        return a == b