友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
101. Symmetric Tree
为什么执行结果显示递归更快？而不是队列呢？
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1 / \ 2 2 / \ / \ 3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1 / \ 2 2 \ \ 3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
思路分析
-
一刷
-
二刷
-
三刷
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
77
78
79
80
81
82
83
84
85
86
87
88
89
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
if (Objects.isNull(t1) && Objects.isNull(t2)) {
return true;
}
if (Objects.isNull(t1)||Objects.isNull(t2)) {
return false;
}
return (Objects.equals(t1.val, t2.val))
&& isMirror(t1.left, t2.right)
&& isMirror(t1.right, t2.left);
}
/**
* Runtime: 1 ms, faster than 36.88% of Java online submissions for Symmetric Tree.
*
* Memory Usage: 38.9 MB, less than 43.54% of Java online submissions for Symmetric Tree.
*/
public boolean isSymmetricIterative(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
queue.add(root);
while (!queue.isEmpty()) {
TreeNode t1 = queue.poll();
TreeNode t2 = queue.poll();
if (Objects.isNull(t1) && Objects.isNull(t2)) {
continue;
}
if (Objects.isNull(t1) || Objects.isNull(t2)) {
return false;
}
if (!Objects.equals(t1.val, t2.val)) {
return false;
}
queue.add(t1.left);
queue.add(t2.right);
queue.add(t1.right);
queue.add(t2.left);
}
return true;
}
/**
* Runtime: 228 ms, faster than 36.88% of Java online submissions for Symmetric Tree.
*
* Memory Usage: 92.6 MB, less than 5.44% of Java online submissions for Symmetric Tree.
*/
public boolean isSymmetricBfs(TreeNode root) {
if (Objects.isNull(root)) {
return true;
}
ArrayList<TreeNode> parent = new ArrayList<>();
parent.add(root);
while (!parent.isEmpty()) {
HashSet<TreeNode> nodes = new HashSet<>(parent);
if (nodes.size() == 1 && nodes.contains(null)) {
return true;
}
ArrayList<TreeNode> children = new ArrayList<>(parent.size() * 2);
for (TreeNode node : parent) {
if (Objects.isNull(node)) {
children.add(null);
children.add(null);
} else {
children.add(node.left);
children.add(node.right);
}
}
for (int i = 0; i < children.size() / 2; i++) {
TreeNode left = children.get(i);
TreeNode right = children.get(children.size() - 1 - i);
if (Objects.isNull(left) && Objects.isNull(right)) {
continue;
}
if (Objects.isNull(left) || Objects.isNull(right)) {
return false;
}
if (!Objects.equals(left.val, right.val)) {
return false;
}
}
parent = children;
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-24 16:14
*/
public boolean isSymmetric(TreeNode root) {
return root == null || isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
// 前面已经判断都为null的情况了，
// 这里为了简单，只需要判断一个不为空即可
if (left == null
|| right == null
|| left.val != right.val) {
return false;
}
// 使用 && 会自动中断后续的递归判断
return isSymmetric(left.left, right.right)
&& isSymmetric(left.right, right.left);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-16 17:51:17
*/
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null
|| right == null
|| left.val != right.val) {
return false;
}
return isSymmetric(left.left, right.right)
&& isSymmetric(left.right, right.left);
}