Skip to content

Commit 943aa88

Browse files
committed
剑指offer57
1 parent 4540c62 commit 943aa88

2 files changed

Lines changed: 56 additions & 0 deletions

File tree

SUMMARY.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -162,6 +162,7 @@
162162
* [54.链表中环的入口结点](/algorithm/For-offer/54.md)
163163
* [55.删除链表中重复的结点](/algorithm/For-offer/55.md)
164164
* [56.二叉树的下一个结点](/algorithm/For-offer/56.md)
165+
* [57.对称的二叉树](/algorithm/For-offer/57.md)
165166
* [LeetCode](algorithm/leetcode.md)
166167
- [Distinct Subsequences](/algorithm/LeetCode/Distinct-Subsequences.md)
167168
- [Longest Common Subsequence](/algorithm/LeetCode/Longest-Common-Subsequence.md)

algorithm/For-offer/57.md

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
## 一、题目
2+
3+
请实现一个函数来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。
4+
5+
## 二、解题思路
6+
7+
通常我们有三种不同的二叉树遍历算法,即前序遍历、中序遍历和后序遍历。在这三种遍历算法中,都是先遍历左子结点再遍历右子结点。我们是否可以定义一种遍历算法,先遍历右子结点再遍历左子结点?比如我们针对前序遍历定义一种对称的遍历算法,即先遍历父节点,再遍历它的右子结点,最后遍历它的左子结点。
8+
9+
我们发现可以用过比较二叉树的前序遍历序列和对称前序遍历序列来判断二叉树是不是对称的。如果两个序列一样,那么二叉树就是对称的。
10+
11+
## 三、解题代码
12+
13+
```java
14+
public class Test {
15+
private static class BinaryTreeNode {
16+
private int val;
17+
private BinaryTreeNode left;
18+
private BinaryTreeNode right;
19+
20+
public BinaryTreeNode() {
21+
}
22+
23+
public BinaryTreeNode(int val) {
24+
this.val = val;
25+
}
26+
27+
@Override
28+
public String toString() {
29+
return val + "";
30+
}
31+
}
32+
33+
public static boolean isSymmetrical(BinaryTreeNode root) {
34+
return isSymmetrical(root, root);
35+
}
36+
37+
private static boolean isSymmetrical(BinaryTreeNode left, BinaryTreeNode right) {
38+
39+
if (left == null && right == null) {
40+
return true;
41+
}
42+
43+
if (left == null || right == null) {
44+
return false;
45+
}
46+
47+
if (left.val != right.val ) {
48+
return false;
49+
}
50+
51+
return isSymmetrical(left.left, right.right) && isSymmetrical(left.right, right.left);
52+
}
53+
}
54+
```
55+

0 commit comments

Comments
 (0)