题目描述
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
100. 相同的树
解法1 递归
树的结构和结点值要相同，使用递归判断当前结点的值是否相同，相同则递归左右结点。
/**
* 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 false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
解法2 迭代
维护一个队列，如果p、q的值相同，则依次将p.left，q.left ，p.right，q.right压入队列，然后下一次循环开始时，就判断队列尾部的p.right和q.right的值是否相同，相同的话，再把它们的左右孩子依次入栈，循环以上过程，直到碰到值不相等或者栈为空。
/**
* 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) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(p);
queue.add(q);
while (!queue.isEmpty()) {
TreeNode tmp1 = queue.remove();
TreeNode tmp2 = queue.remove();
if (tmp1 == null && tmp2 == null) {
continue;
} else if (tmp1 == null || tmp2 == null) {
return false;
} else if (tmp1.val != tmp2.val) {
return false;
}
queue.offer(tmp1.left);
queue.offer(tmp2.left);
queue.offer(tmp1.right);
queue.offer(tmp2.right);
}
//运行到这说明队列已经为空了，而上面的循环是不同时return，到这说明两个数相同。
return true;
}
}
题目描述
给定一个二叉树，检查它是否是镜像对称的
101. 对称二叉树
解法1 递归
与判断两棵二叉树是否相同类似，判断一棵树是否对称，主要判断二叉树的左右子树是否是堆成的，这一部分的代码跟上题几乎一样，差别为输入结点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return helper(root, root);
}
public boolean helper(TreeNode p, TreeNode q) {
if (p == null && q == null) {
//这个true 代表的是这一层传入的 p 和 q 相同
return true;
} else if (p == null || q == null) {
return false;
} else if (p.val != q.val) {
return false;
}
return helper(p.left, q.right) && helper(p.right, q.left);
}
}
解法2 迭代
维护一个队列，单独判断输入树为空的情况，往队列中入队根的左右孩子，接下来的迭代过程每次从队列中取出两个结点判断是否相同，相同则将这两个结点的左右孩子共四个结点入队继续迭代，注意入队顺序应是树结构对称的结点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
boolean isroot = true;
//先检查root == null的情况
if (root == null) {
return true;
}
//把根左右孩子入队
queue.add(root.left);
queue.add(root.right);
while (!queue.isEmpty()) {
//每次从队列中取两个结点出来比较
TreeNode p = queue.remove();
TreeNode q = queue.remove();
if (p == null && q == null) {
continue;
} else if (p == null || q == null) {
return false;
} else if (p.val != q.val) {
return false;
}
//二叉树是否对称，注意入队顺序在树结构中要对称
queue.add(p.left);
queue.add(q.right);
queue.add(p.right);
queue.add(q.left);
}
return true;
}
}
