Algorithm Puzzles ~~everyday~~ ~~every week~~ sometimes: Same Tree

## Puzzle

Puzzle from leetcode:

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.

## Solution

It’s an easy puzzle can be resolved via dfs or bfs, here I use dfs:

1 | class Solution { |

TC should be O(n) and SC should be O(h) where n is node number and h is tree height.