每日一道 LeetCode (20)：相同的树
共 2934字，需浏览 6分钟
·
2020-08-18 11:58
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
代码仓库
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：相同的树
题目来源：https://leetcode-cn.com/problems/same-tree/
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 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
解题思路
今天又见到新的数据结构了，这次遇到的是树，或者简单的说是二叉树。
例行惯例，第一次的见的数据结构基本上都没啥想法，直接看答案。
只能怨自己肚子里墨水太少，不会的太多，搞不定的只能答案走起，算法这玩意，答案背多了再遇到题也就有想法了。
先放一段树的结构代码：
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {}
public TreeNode(int val) { this.val = val; }
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
这段代码很简单，树上的值是 int 类型，然后有一个左节点有一个右节点。
树结构介绍完毕，接下来梳理两种遍历树的方案，或者说是常规操作。
解题的话提供两种方案，一种是递归，一种是循环。
「递归」
首先极限值判断，两个二叉树都为空肯定相等，如果一个为空另一个不为空肯定不相等。
接下来如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同，然后接着递归这个过程。
「循环」
首先和上面一样，先进行极限值判断。
使用两个队列分别存储两个二叉树的节点。初始时将两个二叉树的根节点分别加入两个队列。每次从两个队列各取出一个节点，进行操作：
比较两个节点的值，如果两个节点的值不相同则两个二叉树一定不同。 如果两个节点的值相同，则判断两个节点的子节点是否为空，如果只有一个节点的左子节点为空，或者只有一个节点的右子节点为空，则两个二叉树的结构不同，因此两个二叉树一定不同。 如果两个节点的子节点的结构相同，则将两个节点的非空子节点分别加入两个队列，子节点加入队列时需要注意顺序，如果左右子节点都不为空，则先加入左子节点，后加入右子节点。
结果，如果循环结束的时候两个队列同时为空，那么这两个二叉树相同，如果有一个不为空，那肯定不相同。
代码：
// 迭代
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
} else if (p == null || q == null) {
return false;
} else if (p.val != q.val) {
return false;
} else {
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
// 循环
public boolean isSameTree_1(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
Queue queue1 = new LinkedList<>();
Queue queue2 = new LinkedList<>();
queue1.offer(p);
queue2.offer(q);
while (!queue1.isEmpty() && !queue2.isEmpty()) {
TreeNode node1 = queue1.poll();
TreeNode node2 = queue2.poll();
if (node1.val != node2.val) return false;
TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
if (left1 == null ^ left2 == null) return false;
if (right1 == null ^ right2 == null) return false;
if (left1 != null) queue1.offer(left1);
if (right1 != null) queue1.offer(right1);
if (left2 != null) queue2.offer(left2);
if (right2 != null) queue2.offer(right2);
}
return queue1.isEmpty() && queue2.isEmpty();
}
结果我就不贴了，基本上答案区就这么两种解题方式，也没其他能玩出花来的方式。
