# 100.Same-Tree

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/same-tree/

## ้ข็ฎๆ่ฟฐ

``````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.

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``````

## ไปฃ็ 

### Approach #1 Recursion

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null)    return true;
if (p == null || q == null)    return false;
if (p.val != q.val)    return false;

return isSameTree(p.right, q.right)
&& isSameTree(p.left, q.left);
}
}``````

### Approach #2 Iteration

``````class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (!check(p, q)) return false;

ArrayDeque<TreeNode> deqP = new ArrayDeque<TreeNode>();
ArrayDeque<TreeNode> deqQ = new ArrayDeque<TreeNode>();

while (!deqP.isEmpty()) {
p = deqP.removeFirst();
q = deqQ.removeFirst();

if (!check(p, q))        return false;
if (p != null) {
if (!check(p.left, q.left))    return false;
if (p.left != null) {
}

if (!check(p.right, q.right))    return false;
if (p.right != null) {
}
}
}
return true;
}

public boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null)        return true;
if (p == null || q == null)        return false;
if (p.val != q.val)    return false;

return true;
}

}``````

Last updated