题目给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。示例 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) { // 有一个为null return 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; }相关阅读技术文章汇总【Leetcode】98. 验证二叉搜索树【Leetcode】95~96 不同的二叉搜索树