100. Same Tree (Python)

Related Topic

Depth-First-Search. Tree.

Description

Given two binary trees, 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.

Sample I/O

Example 1

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

Methodology

Use DFS to flatten both trees’ nodes into two arrays. Compare two arrays if they are equal then two trees are same return true otherwise return false

Code

def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def flattenTree(root, flatten_array):
            if not root:
                flatten_array.append(None)
                return
            flatten_array.append(root.val)
            flattenTree(root.left, flatten_array)
            flattenTree(root.right, flatten_array)
            return flatten_array
        p_array = flattenTree(p, [])
        q_array = flattenTree(q, [])
        return p_array == q_array

BigO

Time complexity: O(n) where n is the number of the nodes of both trees.