Skip to content

Commit 98042a9

Browse files
linwtlinwt
committed
二叉树遍历
1 parent 72837e5 commit 98042a9

File tree

4 files changed

+447
-3
lines changed

4 files changed

+447
-3
lines changed

‎leetcode_Java/Solution0094.java

Lines changed: 110 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,6 @@
1+
// 二叉树的中序遍历
2+
3+
14
/**
25
* Definition for a binary tree node.
36
* public class TreeNode {
@@ -14,10 +17,36 @@
1417
* }
1518
*/
1619

17-
// 二叉树的中序遍历
18-
class Solution0094 {
19-
List<Integer> list = new ArrayList<>();
2020

21+
/*
22+
* 递归思路：
23+
* 1、定义数据结构：使用列表成员变量，存储每次递归操作存入的值
24+
* 2、递归终止条件：节点为空时返回
25+
* 3、主要数据操作：把节点的值存入列表
26+
* 4、递归逻辑：
27+
* 左右节点需要与根节点做同样的事，就要用递归
28+
* 确定递归顺序/遍历顺序，左中右
29+
* 每层不需要接收使用递归方法返回值，列表成员变量存储了结果
30+
* */
31+
class Solution {
32+
public List<Integer> list = new ArrayList<>();
33+
public List<Integer> inorderTraversal(TreeNode root) {
34+
if (root == null) {
35+
return list;
36+
}
37+
inorderTraversal(root.left);
38+
list.add(root.val);
39+
inorderTraversal(root.right);
40+
return list;
41+
}
42+
}
43+
44+
45+
/*
46+
* 递归思路：等同上个实现的逻辑
47+
* */
48+
class Solution {
49+
public List<Integer> list = new ArrayList<>();
2150
public List<Integer> inorderTraversal(TreeNode root) {
2251
if (root != null) {
2352
inorderTraversal(root.left);
@@ -26,4 +55,82 @@ public List<Integer> inorderTraversal(TreeNode root) {
2655
}
2756
return list;
2857
}
58+
}
59+
60+
61+
/*
62+
* 迭代思路：
63+
* 1、定义数据结构：局部变量即可，列表存放结果数据，栈按序存放节点，指针指向下一个要处理的节点
64+
* 2、遍历条件、操作逻辑：
65+
* 当前节点不为空，节点入栈，指向左节点
66+
* 栈不为空，弹出节点，存入节点值，指向右节点
67+
* 3、实现了中序遍历，按序存放节点入栈，按序获取节点值
68+
* */
69+
class Solution {
70+
public List<Integer> inorderTraversal(TreeNode root) {
71+
List<Integer> list = new ArrayList<>();
72+
Stack<TreeNode> stack = new Stack<>();
73+
TreeNode cur = root;
74+
while (cur != null || !stack.isEmpty()) {
75+
if (cur != null) {
76+
stack.push(cur);
77+
cur = cur.left;
78+
} else {
79+
cur = stack.pop();
80+
list.add(cur.val);
81+
cur = cur.right;
82+
}
83+
}
84+
return list;
85+
}
86+
}
87+
88+
89+
/*
90+
* 迭代思路：等同上个实现的逻辑
91+
* */
92+
class Solution {
93+
public List<Integer> inorderTraversal(TreeNode root) {
94+
List<Integer> list = new ArrayList<>();
95+
Stack<TreeNode> stack = new Stack<>();
96+
TreeNode cur = root;
97+
while (cur != null || !stack.isEmpty()) {
98+
while (cur != null) {
99+
stack.push(cur);
100+
cur = cur.left;
101+
}
102+
cur = stack.pop();
103+
list.add(cur.val);
104+
cur = cur.right;
105+
}
106+
return list;
107+
}
108+
}
109+
110+
111+
/*
112+
* 莫里斯遍历：用递归和迭代的方式都使用了辅助的空间，而莫里斯遍历的优点是没有使用任何辅助空间。
113+
* 缺点是改变了整个树的结构，强行把一棵二叉树改成一段链表结构。
114+
* 思路：把根节点接到左子树的最后一个右节点上，形成链表，再遍历获取链表的值
115+
* */
116+
class Solution {
117+
public List<Integer> inorderTraversal(TreeNode root) {
118+
List<Integer> list = new ArrayList<>();
119+
while (root != null) {
120+
if (root.left != null) {
121+
TreeNode pre = root.left;
122+
while (pre.right != null) {
123+
pre = pre.right;
124+
}
125+
pre.right = root;
126+
TreeNode temp = root;
127+
root = root.left;
128+
temp.left = null;
129+
} else {
130+
list.add(root.val);
131+
root = root.right;
132+
}
133+
}
134+
return list;
135+
}
29136
}

‎leetcode_Java/Solution0102.java

Lines changed: 133 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,133 @@
1+
// 二叉树的层序遍历
2+
3+
4+
/**
5+
* Definition for a binary tree node.
6+
* public class TreeNode {
7+
* int val;
8+
* TreeNode left;
9+
* TreeNode right;
10+
* TreeNode() {}
11+
* TreeNode(int val) { this.val = val; }
12+
* TreeNode(int val, TreeNode left, TreeNode right) {
13+
* this.val = val;
14+
* this.left = left;
15+
* this.right = right;
16+
* }
17+
* }
18+
*/
19+
20+
21+
/*
22+
* 迭代思路：
23+
* 1、定义数据结构：二维列表存放结果；队列按序存放每层节点；临时子列表存放每层节点值
24+
* 2、辅助标记：整型变量标记每层在队列的节点个数，以便维护二维列表
25+
* 3、实现逻辑：遍历当层节点，节点值存入子列表，下一层节点从左到右按序存入队列，循环遍历队列节点
26+
* 4、队列：先进先出，尾部存入，头部移除
27+
* */
28+
class Solution {
29+
public List<List<Integer>> levelOrder(TreeNode root) {
30+
List<List<Integer>> list = new ArrayList<>();
31+
if (root == null) {
32+
return list;
33+
}
34+
List<Integer> sonList = new ArrayList<>();
35+
Queue<TreeNode> queue = new LinkedList<>();
36+
queue.add(root);
37+
int count;
38+
while (!queue.isEmpty()) {
39+
count = queue.size();
40+
while (count > 0) {
41+
root = queue.remove();
42+
sonList.add(root.val);
43+
if (root.left != null) {
44+
queue.add(root.left);
45+
}
46+
if (root.right != null) {
47+
queue.add(root.right);
48+
}
49+
count--;
50+
}
51+
list.add(sonList);
52+
sonList = new ArrayList<>();
53+
}
54+
return list;
55+
}
56+
}
57+
58+
59+
/*
60+
* 迭代思路：
61+
* 1、定义数据结构：二维列表存放结果；队列按序存放每层节点；临时子列表存放每层节点值
62+
* 2、辅助标记：在队列中，每一层的尾部添加哨兵，标记该层的结束位置
63+
* 2、实现逻辑：
64+
* 1）先将根节点和哨兵加入队列，初始化第一层
65+
* 2）通过对象类型区分节点与哨兵。
66+
* 如果是节点，则将节点值存入子列表，将左右节点存入队列。
67+
* 如果是哨兵，表示当前层结束，将子列表存入结果列表。如果队列还有元素即还有下一层，则创建新的子列表存放下一层节点值，在队列尾部添加哨兵，标记下一层的结束位置
68+
* */
69+
class Solution {
70+
public List<List<Integer>> levelOrder(TreeNode root) {
71+
List<List<Integer>> list = new ArrayList<>();
72+
if (root == null) {
73+
return list;
74+
}
75+
List<Integer> sonList = new ArrayList();
76+
Queue<Object> queue = new LinkedList<>();
77+
queue.add(root);
78+
queue.add(0);
79+
while (!queue.isEmpty()) {
80+
Object obj = queue.remove();
81+
if (obj instanceof TreeNode) {
82+
TreeNode node = (TreeNode) obj;
83+
sonList.add(node.val);
84+
if (node.left != null) {
85+
queue.add(node.left);
86+
}
87+
if (node.right != null) {
88+
queue.add(node.right);
89+
}
90+
} else {
91+
list.add(sonList);
92+
if (!queue.isEmpty()) {
93+
sonList = new ArrayList();
94+
queue.add(0);
95+
}
96+
}
97+
}
98+
return list;
99+
}
100+
}
101+
102+
103+
/*
104+
* 递归思路：
105+
* 1、定义数据结构：成员变量：列表存放递归结果
106+
* 局部变量：子列表存放每层节点值
107+
* 2、辅助标记：整型变量标记 层的深度 对应 子列表的索引
108+
* 3、递归逻辑：
109+
* 1）前序遍历，深度优先搜索，每个节点都会遍历到，每层节点最终都是从左到后按序访问
110+
* 2）记录节点所在层的深度，每到新的一层就创建一个新的子列表，层的深度对应子列表的索引，节点值层序存放
111+
* */
112+
class Solution {
113+
public List<List<Integer>> list = new ArrayList<>();
114+
115+
public List<List<Integer>> levelOrder(TreeNode root) {
116+
return dfs(root, 0);
117+
}
118+
119+
public List<List<Integer>> dfs(TreeNode root, int deep) {
120+
if (root == null) {
121+
return list;
122+
}
123+
deep++;
124+
if (list.size() < deep) {
125+
List<Integer> sonList = new ArrayList<>();
126+
list.add(sonList);
127+
}
128+
list.get(deep - 1).add(root.val);
129+
dfs(root.left, deep);
130+
dfs(root.right, deep);
131+
return list;
132+
}
133+
}

‎leetcode_Java/Solution0144.java

Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,124 @@
1+
// 二叉树的前序遍历
2+
3+
4+
/**
5+
* Definition for a binary tree node.
6+
* public class TreeNode {
7+
* int val;
8+
* TreeNode left;
9+
* TreeNode right;
10+
* TreeNode() {}
11+
* TreeNode(int val) { this.val = val; }
12+
* TreeNode(int val, TreeNode left, TreeNode right) {
13+
* this.val = val;
14+
* this.left = left;
15+
* this.right = right;
16+
* }
17+
* }
18+
*/
19+
20+
21+
/*
22+
* 递归思路：
23+
* 1、定义数据结构：使用列表成员变量，存储每次递归操作存入的值
24+
* 2、递归终止条件：节点为空时返回
25+
* 3、主要数据操作：把节点的值存入列表
26+
* 4、递归逻辑：
27+
* 左右节点需要与根节点做同样的事，就要用递归
28+
* 确定递归顺序/遍历顺序，中左右
29+
* 每层不需要接收使用递归方法返回值，列表成员变量存储了结果
30+
* */
31+
class Solution {
32+
public List<Integer> list = new ArrayList<>();
33+
public List<Integer> preorderTraversal(TreeNode root) {
34+
if (root == null) {
35+
return list;
36+
}
37+
list.add(root.val);
38+
preorderTraversal(root.left);
39+
preorderTraversal(root.right);
40+
return list;
41+
}
42+
}
43+
44+
45+
/*
46+
* 迭代思路：
47+
* 1、定义数据结构：局部变量即可，列表存放结果数据，栈按序存放节点，指针指向下一个要处理的节点
48+
* 2、遍历条件、操作逻辑：
49+
* 如果当前节点为空，则从栈弹出节点
50+
* 存入当前节点值；右节点入栈，用来后面获取右节点的值；指向左节点
51+
* */
52+
class Solution {
53+
public List<Integer> preorderTraversal(TreeNode root) {
54+
List<Integer> list = new ArrayList<>();
55+
Stack<TreeNode> stack = new Stack<>();
56+
TreeNode cur = root;
57+
while (cur != null || !stack.isEmpty()) {
58+
if (cur == null) {
59+
cur = stack.pop();
60+
}
61+
list.add(cur.val);
62+
if (cur.right != null) {
63+
stack.push(cur.right);
64+
}
65+
cur = cur.left;
66+
}
67+
return list;
68+
}
69+
}
70+
71+
72+
/*
73+
* 迭代思路：
74+
* 1、定义数据结构：局部变量即可，列表存放结果数据，栈按序存放节点，指针指向下一个要处理的节点
75+
* 2、遍历条件、操作逻辑：
76+
* 存入当前节点值；当前节点入栈，用来后面获取右节点；指向左节点
77+
* */
78+
class Solution {
79+
public List<Integer> preorderTraversal(TreeNode root) {
80+
List<Integer> list = new ArrayList<>();
81+
Stack<TreeNode> stack = new Stack<>();
82+
TreeNode cur = root;
83+
while (cur != null || !stack.isEmpty()) {
84+
while (cur != null) {
85+
list.add(cur.val);
86+
stack.push(cur);
87+
cur = cur.left;
88+
}
89+
cur = stack.pop();
90+
cur = cur.right;
91+
}
92+
return list;
93+
}
94+
}
95+
96+
97+
/*
98+
* 迭代思路：
99+
* 1、定义数据结构：局部变量即可，列表存放结果数据，栈按序存放节点
100+
* 2、遍历条件、操作逻辑：
101+
* 存入当前节点值；右节点入栈；左节点入栈
102+
* 3、用左节点入栈弹出的方式代替了指针标记下一个要处理的节点
103+
* */
104+
class Solution {
105+
public List<Integer> preorderTraversal(TreeNode root) {
106+
List<Integer> list = new ArrayList<>();
107+
Stack<TreeNode> stack = new Stack<>();
108+
if (root == null) {
109+
return list;
110+
}
111+
stack.push(root);
112+
while (!stack.isEmpty()) {
113+
root = stack.pop();
114+
list.add(root.val);
115+
if (root.right != null) {
116+
stack.push(root.right);
117+
}
118+
if (root.left != null) {
119+
stack.push(root.left);
120+
}
121+
}
122+
return list;
123+
}
124+
}

0 commit comments

Comments
 (0)