题目

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入:       1         1/ \       / \2   3     2   3[1,2,3],   [1,2,3]输出: true

示例 2:
输入:      1          1/           \2             2[1,2],     [1,null,2]输出: false

示例 3::
输入:       1         1/ \       / \2   1     1   2[1,2,1],   [1,1,2]输出: false

题解

大多数的二叉树题目都是用递归可以解的。
所以当拿到二叉树的题目的时候，我们首先就是看看能拆解成哪些子问题。
这个问题的子问题很简单，就是左子树，右子树都相等的二叉树是相同的二叉树。

/*** 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;} else if (p == null || q == null) {return false;}if (p.val == q.val) {return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);} else {return false;}}
}

那如果用非递归解怎么解呢?
如果遇到二叉树的问题，没思路还有第二招，就是想想看是不是遍历的变种：

先序遍历
中序遍历
后序遍历
层次遍历

我们可以用队列，一起进行层序遍历，同时比较左右两颗树:

/*** 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;} else if (p == null || q == null) {return false;}LinkedList<TreeNode> queue = new LinkedList<>();queue.add(p);queue.add(q);while(!queue.isEmpty()) {TreeNode left = queue.poll();TreeNode right = queue.poll();if (left == null && right == null) {// 都是空的,遍历到叶子节点了continue;} else if (left == null || right == null) {// 有一个为nullreturn false;} else if (left.val != right.val) {// 不相等.return false;}// 左子树入队queue.add(left.left);queue.add(right.left);// 右子树入队queue.add(left.right);queue.add(right.right);}return true;}
}

其实我们本质上就是要比较左右两棵树,也没必要非要是队列,其实stack也是可以的,大同小异。所以并不是你记住哪种数据结构，关键是你能理解后，灵活应用.

    public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;} else if (p == null || q == null) {return false;}Stack<TreeNode> stack = new Stack<>();stack.push(p);stack.push(q);while(!stack.isEmpty()) {TreeNode left = stack.pop();TreeNode right = stack.pop();if (left == null && right == null) {continue;} else if (left == null || right == null) {return false;} else if (left.val != right.val) {return false;}stack.push(left.left);stack.push(right.left);stack.push(left.right);stack.push(right.right);}return true;}