# LC 100. Same Tree

### [Problem link](https://leetcode.com/problems/same-tree/)

###### tags: `leedcode` `python` `c++` `easy` `DFS` `Binary Tree`

Given the roots of two binary trees <code>p</code> and <code>q</code>, 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:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/20/ex1.jpg" style="width: 622px; height: 182px;" />

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

**Example 2:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/20/ex2.jpg" style="width: 382px; height: 182px;" />

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

**Example 3:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/20/ex3.jpg" style="width: 622px; height: 182px;" />

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

**Constraints:**

- The number of nodes in both trees is in the range <code>[0, 100]</code>.
- <code>-10⁴ <= Node.val <= 10⁴</code>

## Solution 1 - recursion
#### Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def dfs(s, t):
            if s and t and s.val == t.val:
                return dfs(s.left, t.left) and dfs(s.right, t.right)

            return s == t

        return dfs(p, q)
            

#### C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr || q == nullptr) {
            return p == q;
        }
        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

## Solution 2 - Iteration
#### C++

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode *> qu;

        qu.push(p);
        qu.push(q);

        while (!qu.empty()) {
            TreeNode *tmp = qu.front();
            qu.pop();
            TreeNode *tmp2 = qu.front();
            qu.pop();

            if (tmp == nullptr and tmp2 == nullptr) {
                continue;
            }
            if (tmp == nullptr || tmp2 == nullptr || (tmp->val != tmp2->val)) {
                return false;
            }
            qu.push(tmp->left);
            qu.push(tmp2->left);
            qu.push(tmp->right);
            qu.push(tmp2->right);
        }
        return true;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |
>| Solution 2 | O(n) | O(n) |

## Note
[類似LC 101. Symmetric Tree](https://hackmd.io/@Alone0506/Sy1ODFynh)