1. question: 对称二叉树（简单）
给你一个二叉树的根节点 root ， 检查它是否轴对称。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree
示例 1：
1
2
| 输入：root = [1,2,2,3,4,4,3]
输出：true
|
示例 2：
1
2
| 输入：root = [1,2,2,null,3,null,3]
输出：false
|
提示：
1
2
| 树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
|
2. answers
首先，判断是否是对称二叉树，指的是判断根节点的左右子树是否互为翻转二叉树。那么可以将其一棵子树翻转，然后和另一棵子树按同样的遍历，判断对应位置上的节点是否相等。
仔细想想，其实可以不翻转。就是比较根节点的左右两棵子树，左子树的左节点和右子树的右节点、左子树的右节点和右子树的左节点是否相等。可以采用队列存储节点。入队列的时候，按照对称的位置入队列。出队的时候，一次出队两个，判断两个节点是否相等。如果相等，则继续将第一个节点（左子树），第二个节点（右子树）中对应位置的节点入队。
代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| public class Solution_0023 {
public static boolean isSymmetric(TreeNode root) {
boolean result = true;
if(root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
TreeNode left, right;
while(!queue.isEmpty()) {
left = queue.poll();
right = queue.poll();
if(left == null && right == null) {
continue;
}
if(left != null && right != null) {
if(left.val != right.val) {
result = false;
break;
}
} else {
result = false;
break;
}
queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
return result;
}
public static void main(String[] args) {
System.out.println();
TreeNode tn1 = new TreeNode(3);
TreeNode tn2 = new TreeNode(4);
TreeNode tn3 = new TreeNode(2, tn1, tn2);
TreeNode tn4 = new TreeNode(4);
TreeNode tn5 = new TreeNode(3);
TreeNode tn6 = new TreeNode(2, tn4, tn5);
TreeNode root = new TreeNode(1, tn3, tn6);
System.out.println(isSymmetric(root));
TreeNode tns1 = new TreeNode(3);
TreeNode tns2 = new TreeNode(2, null, tns1);
TreeNode tns3 = new TreeNode(3);
TreeNode tns4 = new TreeNode(2, null, tns3);
TreeNode tns5 = new TreeNode(1, tns2, tns4);
System.out.println(isSymmetric(tns5));
}
}
|
3. 参考
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
