![https://leetcode.com/problems/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

ex1

Example 2:

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

ex2

Example 3:

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

ex3

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -104 <= Node.val <= 104
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
        
        List<TreeNode> queue1 = new ArrayList<>();
        List<TreeNode> queue2 = new ArrayList<>();
        
        queue1.add(p);
        queue2.add(q);
        
        while (!queue1.isEmpty() || !queue2.isEmpty()) {
            
            if (queue1.isEmpty()) {
                return false;
            }
            
            if (queue2.isEmpty()) {
                return false;
            }
            
            TreeNode a = queue1.remove(0);
            TreeNode b = queue2.remove(0);
            
            if (a == null && a == b) {
                continue;
            }

            if (a == null || b == null) {
                return false;
            }

            if (a.val != b.val) {
                return false;
            }
            
            queue1.add(a.left);
            queue2.add(b.left);
            
            queue1.add(a.right);
            queue2.add(b.right);
        }
        
        return true;
    }
    
    public boolean isSameTree2(TreeNode p, TreeNode q) {
        if (p == null && p == q) {
            return true;
        }
        
        if (p == null || q == null) {
            return false;
        }
        
        if (p.val != q.val) {
            return false;
        }
        
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}