题目：
题解：
1. 递归法：
注：
递归的难点在于：找到可以递归的点 为什么很多人觉得递归一看就会，一写就废。 或者说是自己写无法写出来，关键就是你对递归理解的深不深。
对于此题： 递归的点怎么找？从拿到题的第一时间开始，思路如下：
-
怎么判断一棵树是不是对称二叉树？ 答案：如果所给根节点，为空，那么是对称。如果不为空的话，当他的左子树与右子树对称时，他对称
-
那么怎么知道左子树与右子树对不对称呢？在这我直接叫为左树和右树 答案：如果左树的左孩子与右树的右孩子对称，左树的右孩子与右树的左孩子对称，那么这个左树和右树就对称。
仔细读这句话，是不是有点绕？怎么感觉有一个功能A我想实现，但我去实现A的时候又要用到A实现后的功能呢？
当你思考到这里的时候，递归点已经出现了： 递归点：我在尝试判断左树与右树对称的条件时，发现其跟两树的孩子的对称情况有关系。
想到这里，你不必有太多疑问，上手去按思路写代码，函数A（左树，右树）功能是返回是否对称
def 函数A（左树，右树）： 左树节点值等于右树节点值 且 函数A（左树的左子树，右树的右子树），函数A（左树的右子树，右树的左子树）均为真 才返回真
实现完毕。。。
写着写着。。。你就发现你写出来了。。。。。。
2. 迭代法：
代码：
1. 递归法：
/** * code101 */
public class code101 {
public static boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
// 调用递归函数，比较左节点，右节点
return isMirror(root.left, root.right);
}
public static boolean isMirror(TreeNode t1, TreeNode t2) {
// 递归的终止条件是两个节点都为空
// 或者两个节点中有一个为空
// 或者两个节点的值不相等
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null) {
return false;
}
if (t1.val != t2.val) {
return false;
}
// 再递归的比较 左节点的左孩子 和 右节点的右孩子
// 以及比较 左节点的右孩子 和 右节点的左孩子
return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}
public static void main(String[] args) {
System.out.println("***************************************");
Integer num1[] = { 1, 2, 2, 3, 4, 4, 3 };
TreeNode tree1 = ConstructTree.constructTree(num1);
TreeOperation.show(tree1);
boolean flag1 = isSymmetric(tree1);
System.out.println(flag1);
System.out.println("***************************************");
Integer num2[] = { 1, 2, 2, null, 3, null, 3 };
TreeNode tree2 = ConstructTree.constructTree(num2);
TreeOperation.show(tree2);
boolean flag2 = isSymmetric(tree2);
System.out.println(flag2);
System.out.println("***************************************");
}
}
2. 迭代法：
/** * code101 */
import java.util.*;
public class code101 {
// 解法二：迭代
public static boolean isSymmetric(TreeNode root) {
if (root == null || (root.left == null && root.right == null)) {
return true;
}
// 用队列保存节点
Queue<TreeNode> queue = new LinkedList<>();
// 将根节点的左右孩子放到队列中
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
// 从队列中取出两个节点，再比较这两个节点
TreeNode t1 = queue.poll();
TreeNode t2 = queue.poll();
// 如果两个节点都为空就继续循环，两者有一个为空就返回false
if (t1 == null && t2 == null) {
continue;
}
if (t1 == null || t2 == null) {
return false;
}
if (t1.val != t2.val) {
return false;
}
// 将左节点的左孩子， 右节点的右孩子放入队列
queue.offer(t1.left);
queue.offer(t2.right);
// 将左节点的右孩子，右节点的左孩子放入队列
queue.offer(t1.right);
queue.offer(t2.left);
}
return true;
}
public static void main(String[] args) {
System.out.println("***************************************");
Integer num1[] = { 1, 2, 2, 3, 4, 4, 3 };
TreeNode tree1 = ConstructTree.constructTree(num1);
TreeOperation.show(tree1);
boolean flag1 = isSymmetric(tree1);
System.out.println(flag1);
System.out.println("***************************************");
Integer num2[] = { 1, 2, 2, null, 3, null, 3 };
TreeNode tree2 = ConstructTree.constructTree(num2);
TreeOperation.show(tree2);
boolean flag2 = isSymmetric(tree2);
System.out.println(flag2);
System.out.println("***************************************");
}
}
注：
// 这是一个List:
List<String> list = new LinkedList<>();
// 这是一个Queue:
Queue<String> queue = new LinkedList<>();
京公网安备 11010502036488号