华为面试官: 判断两棵二叉树是否相同, 迭代方法实现?

import java.util.*; 
public class Main { 
  
// 二叉树节点
static class Node  
{  
    int data;  
    Node left, right;  
} 
  
// 迭代方法实现,层序遍历 
static boolean areIdentical(Node root1, Node root2)  
{  
    // 1.都为空树,返回true;
    if (root1 == null && root2 == null)  return true;  
  
    // 其中一个为空树,另外一个非空树,返回false 
    if (root1 == null || root2 == null) return false;  
  
    // 创建队列,队列里放置为二叉树节点 
    Queue<Node > q1 = new LinkedList<Node> (); 
    Queue<Node>  q2 = new LinkedList<Node> ();  
  
    // 添加树节点到队列 
    q1.add(root1);  
    q2.add(root2);  
    // 两个队列非空时,开始比较
    while (!q1.isEmpty() && !q2.isEmpty())  
    {  
        // 得到节点,比较
        Node n1 = q1.peek();  
        Node n2 = q2.peek();  
  
        if (n1.data != n2.data)  
        return false;  
  
        // 如果数据相等, 在队列里删除节点 
        q1.remove(); 
        q2.remove();  
  
       
        // 比较相同节点的左子树 , 两棵二叉树的左子树都非空时
        if (n1.left != null && n2.left != null)  
        {  
            q1.add(n1.left);  
            q2.add(n2.left);  
        }  
  
        // 一棵左子树非空, 另一棵左子树空时
        else if (n1.left != null || n2.left != null)  
            return false;  
  
        
        //同理, 比较右子树
        if (n1.right != null && n2.right != null)  
        {  
            q1.add(n1.right);  
            q2.add(n2.right);  
        }  
        else if (n1.right != null || n2.right != null)  
            return false;  
    }  
  
    return true;  
}  
  

static Node newNode(int data)  
{  
    Node temp = new Node();  
    temp.data = data;  
    temp.left = null; 
    temp.right = null;  
    return temp;  
}  
  

public static void main(String[] args)  
{  
    Node root1 = newNode(1);  
    root1.left = newNode(2);  
    root1.right = newNode(3);  
    root1.left.left = newNode(4);  
    root1.left.right = newNode(5);  
  
    Node root2 = newNode(1);  
    root2.left = newNode(2);  
    root2.right = newNode(3);  
    root2.left.left = newNode(4);  
    root2.left.right = newNode(5);  
  
    if(areIdentical(root1, root2) == true) 
        return true; 
    else
        return false; 
} 
}