作者: 码蹄疾 毕业于哈尔滨工业大学。 小米广告第三代广告引擎的设计者、开发者； 负责小米应用商店、日历、开屏广告业务线研发； 主导小米广告引擎多个模块重构； 关注推荐、搜索、广告领域相关知识;
题目
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 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 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 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; }复制代码