Skip to content

Commit c86af9f

Browse files
gzc426gzc426
authored
Merge pull request gzc426#393 from fsd2018/patch-6
Create 铁男神sama.md
2 parents 0527d0f + 46e9e81 commit c86af9f

File tree

1 file changed

+214
-0
lines changed

1 file changed

+214
-0
lines changed

‎2018.12.05-leetcode102/铁男神sama.md

Lines changed: 214 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,214 @@
1+
2+
3+
4+
5+
## 101.对称二叉树
6+
7+
> [https://leetcode-cn.com/problems/binary-tree-level-order-traversal/](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
8+
9+
### 一、题目
10+
11+
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
12+
13+
例如:给定二叉树: `[3,9,20,null,null,15,7]`,
14+
15+
```
16+
3
17+
/ \
18+
9 20
19+
/ \
20+
15 7
21+
```
22+
23+
返回其层次遍历结果：
24+
25+
```
26+
[
27+
[3],
28+
[9,20],
29+
[15,7]
30+
]
31+
```
32+
33+
### 二、思路
34+
35+
- **层序遍历回顾：** 用队列。将根结点入队，只要队列不为空，就每次从队列中出队一个结点，打印它的值，如果当前出队的这个结点有左孩子，左孩子入队，有右孩子，则右孩子入队。
36+
37+
```java
38+
/*不换行*/
39+
public void printByLevel(TreeNode root) {
40+
if(root==null)return;
41+
Queue<TreeNode> q = new LinkedList<>();
42+
q.offer(root);
43+
44+
while(!q.isEmpty()) {
45+
TreeNode popNow = q.poll();
46+
System.out.print(popNow.val);
47+
System.out.print(" ");
48+
if(popNow.left!=null) {
49+
q.offer(popNow.left);
50+
}
51+
if(popNow.right!=null) {
52+
q.offer(popNow.right);
53+
}
54+
}
55+
System.out.println();
56+
}
57+
/*换行：
58+
层序遍历打印二叉树是个很简单的问题，但是此题要求换行，不是简单的层序遍历了。关键问题就是需要去确定何时该换行。这就需要两个TreeNode类型的变量last和nLast。last表示正在打印的当前行最右节点，nLast表示下一行的最右结点。*/
59+
public void printBylevel1(TreeNode root) {
60+
if (root == null)
61+
return;
62+
63+
Queue<TreeNode> q = new LinkedList<>();
64+
int level = 1;
65+
TreeNode last = root;
66+
TreeNode nLast = null;
67+
q.offer(root);
68+
System.out.printf("Level%d:", level++);
69+
while (!q.isEmpty()) {
70+
TreeNode popNow = q.poll();
71+
System.out.print(popNow.val + " ");
72+
73+
if (popNow.left != null) {
74+
q.offer(popNow.left);
75+
nLast = popNow.left;
76+
}
77+
if (popNow.right != null) {
78+
q.offer(popNow.right);
79+
nLast = popNow.right;
80+
}
81+
if (popNow == last && !q.isEmpty()) {
82+
last = nLast;
83+
System.out.printf("\nLevel%d:", level++);
84+
}
85+
}
86+
System.out.println();
87+
}
88+
```
89+
90+
91+
92+
### 三、题解
93+
94+
#### 这是第一次ac：首先想到的是左神教的last和nlast做法，没能一次成功。于是画图，发现列队size()配合上BFS就能解出本题。
95+
96+
```java
97+
/**
98+
* Definition for a binary tree node.
99+
* public class TreeNode { int val; TreeNode
100+
* left; TreeNode right; TreeNode(int x) { val = x; } }
101+
*/
102+
class Solution {
103+
public List<List<Integer>> breadthTraverse(TreeNode root) {
104+
List<List<Integer>> listAll = new ArrayList<>();
105+
Queue<TreeNode> q = new LinkedList<>();
106+
q.offer(root);
107+
if(root==null)return listAll;
108+
while (!q.isEmpty()) {
109+
List<Integer> list = new ArrayList<>();
110+
int size = q.size();
111+
for (int i = 0; i < size; i++) {
112+
//System.out.printf("size=%d\n",size);
113+
TreeNode popNow = q.poll();
114+
list.add(popNow.val);
115+
if (popNow.left != null) {
116+
q.offer(popNow.left);
117+
}
118+
if (popNow.right != null) {
119+
q.offer(popNow.right);
120+
}
121+
}
122+
listAll.add(list);
123+
}
124+
return listAll;
125+
}
126+
}
127+
```
128+
129+
#### 这是第二次ac：比较蠢，非要用左神的last和nlast，这回倒好了，直接解析String。。怎么说呢，有点无脑，好在8ms还可以接受。
130+
131+
```java
132+
public List<List<Integer>> levelOrder(TreeNode root) {
133+
List<List<Integer>> listAll = new ArrayList<>();
134+
if (root == null)
135+
return listAll;
136+
String s = printBylevel2(root);
137+
String[] sArray = s.split("\n");
138+
for (int i = 0; i < sArray.length; i++) {
139+
List<Integer> list = new ArrayList();
140+
for (String ss : sArray[i].split(" ")) {
141+
list.add(Integer.parseInt(ss));
142+
}
143+
listAll.add(list);
144+
}
145+
// System.out.println("TorF?");
146+
return listAll;
147+
}
148+
149+
public String printBylevel2(TreeNode root) {
150+
if (root == null)
151+
return "";
152+
StringBuilder sb = new StringBuilder();
153+
Queue<TreeNode> q = new LinkedList<>();
154+
int level = 1;
155+
TreeNode last = root;
156+
TreeNode nLast = null;
157+
q.offer(root);
158+
159+
while (!q.isEmpty()) {
160+
TreeNode popNow = q.poll();
161+
sb.append(popNow.val + " ");
162+
163+
if (popNow.left != null) {
164+
q.offer(popNow.left);
165+
nLast = popNow.left;
166+
}
167+
if (popNow.right != null) {
168+
q.offer(popNow.right);
169+
nLast = popNow.right;
170+
}
171+
if (popNow == last && !q.isEmpty()) {
172+
last = nLast;
173+
sb.append("\n");
174+
}
175+
}
176+
return sb.toString();
177+
}
178+
```
179+
180+
#### 这是第三次ac：在上面的基础上，发现了小秘密，其实只要在左神的解法上稍作改动就能完成此题。
181+
182+
```java
183+
public List<List<Integer>> levelOrder(TreeNode root) {
184+
List<List<Integer>> listAll = new ArrayList<>();
185+
if (root == null)
186+
return listAll;
187+
Queue<TreeNode> q = new LinkedList<>();
188+
int level = 1;
189+
TreeNode last = root;
190+
TreeNode nLast = null;
191+
q.offer(root);
192+
List<Integer> list = new ArrayList();
193+
while (!q.isEmpty()) {
194+
int size = q.size();
195+
TreeNode popNow = q.poll();
196+
list.add(popNow.val);
197+
if (popNow.left != null) {
198+
q.offer(popNow.left);
199+
nLast = popNow.left;
200+
}
201+
if (popNow.right != null) {
202+
q.offer(popNow.right);
203+
nLast = popNow.right;
204+
}
205+
if (popNow == last) {
206+
last = nLast;
207+
listAll.add(list);
208+
list=new ArrayList<Integer>();
209+
}
210+
}
211+
return listAll;
212+
}
213+
```
214+

0 commit comments

Comments
 (0)