广度优先遍历,依次访问2颗树的每一个节点并经行比较
时间O(n),空间O(n)
public boolean isSameTree(TreeNode p, TreeNode q) { Deque<TreeNode> queue1 = new LinkedList<TreeNode>(); Deque<TreeNode> queue2 = new LinkedList<TreeNode>(); queue1.add(p); queue2.add(q); while(!queue1.isEmpty() && !queue2.isEmpty()){ TreeNode temp1 = queue1.poll(); TreeNode temp2 = queue2.poll(); if (temp1==null && temp2==null) continue; if (temp1==null || temp2==null) return false; if (temp1.val!=temp2.val) return false; queue1.add(temp1.left); queue1.add(temp1.right); queue2.add(temp2.left); queue2.add(temp2.right); } return queue1.isEmpty() && queue2.isEmpty(); }