题目
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
解题思路
这道题的解题思路比较简单,就是同时遍历两颗树的问题,并比较每个遍历的结点的值是否相等即可。问题就变成了怎么遍历,根据树型知识
)里描述的,我们有很多种遍历的方法可以选择,通过深度优先和广度优先都可以,每种优先都可以使用递归和迭代实现。先看递归解决方案
递归解法
先找子问题,两颗树相同,就是根节点相同,并且左右子树也符合这个要求,那么子问题就是每个遍历到的结点都相同。终止条件就是两个结点是否相同的条件。我们就可以上述的分解办法,不断的迭代这个子问题。
递归解法代码
/**
* 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;
}else if(p.val != q.val){
return false;
}
//子问题:如果左右子树都是相同的树,那么就是相同的树
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
迭代解法
对于迭代,我们可以深度优先或者广度优先,深度优先就是栈,后入先出的数据结构,遍历两颗树,比较每一个迭代到的结点。或者使用广度优先,层序遍历两颗树,也是比较每一个被遍历到的结点,方法很多,大家可以每一种都试试,这里只用栈结构的前序遍历完成解题。先看下怎么使用单个栈完成前序遍历
如何使用栈实现前序遍历
上面这棵树的前序遍历是:FCADBEHGM
我们拿到一个栈
先放入根节点F (栈结构:F)
取出栈顶元素并输出F (栈结构:空)
然后放入他的右子树和左子树(EC)
取出栈顶并输出C (E)
然后放入他的右子树和左子树(ADE),
....循环上面的步骤,直到栈为空,就完成了前序遍历的过程
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
//先放入根节点
stack.push(root);
while (!stack.isEmpty()) {
//执行循环体,先取出栈顶元素并输出,并依次放入右左结点
TreeNode node = stack.pop();
res.add(Integer.valueOf(node.val));
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return res;
}
迭代解法代码
上面给出了使用栈实现前序遍历的代码,我们只要同时对两颗树进行操作即可,并判断每一个遍历到的结点
public boolean isSameTreePre(TreeNode p, TreeNode q) {
if (p == null && q == null){
return true;
}
if (p == null){
return false;
}
if (q == null){
return false;
}
Stack<TreeNode> stackP = new Stack<>();
stackP.add(p);
Stack<TreeNode> stackQ = new Stack<>();
stackQ.add(q);
while (!stackP.isEmpty() || !stackQ.isEmpty()) {
TreeNode pNode = stackP.pop();
TreeNode qNode = stackQ.pop();
if (pNode == null && qNode == null) continue;
if (pNode == null) return false;
if (qNode == null) return false;
if (pNode.val != qNode.val) {
return false;
} else {
stackP.add(pNode.right);
stackQ.add(qNode.right);
stackP.add(pNode.left);
stackQ.add(qNode.left);
}
}
return true;
}
网友评论