# [leetcode] 100. Same Tree _ Algorithm Problem Solve for python

## 1. Problem

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].
• -10^4 <= Node.val <= 10^4

## 2. Solution

I solved this problem like this.

• Make two list ans1, ans2.
• Using dfs, put node on list.
• Check now node. Append node value on list and return if node is None value.
• Check left, right node. If node has child, go to dfs. If node don’t have child, append node value.
• All node are inserted, check two list have same value.
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
def dfs(node, ans):
if not node:
ans.append(node)
return
ans.append(node.val)
dfs(node.left, ans) if node.left else ans.append(node.left)
dfs(node.right, ans) if node.right else ans.append(node.right)

ans1, ans2 = [], []
dfs(p, ans1), dfs(q, ans2)
return ans1 == ans2