[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


  • 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:
            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