本节内容
理论基础※
建议：需要了解 二叉树的种类，存储方式，遍历方式 以及二叉树的定义
文章讲解： https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%A7%8D%E7%B1%BB
二叉树理论基础
递归遍历※
建议：二叉树的三种递归遍历掌握其规律后，其实很简单
文章讲解： https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html
递归遍历三步走
1、确认递归函数的参数和返回值
2、确定终止条件
3、确认单层递归的逻辑
全面理解递归
144. 二叉树的前序遍历
题目链接： 144. 二叉树的前序遍历
题目分析
递归遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
recur(root, result);
return result;
}
private void recur(TreeNode node, List<Integer> res) {
if (node == null) {
return;
}
res.add(node.val);
recur(node.left, res);
recur(node.right, res);
}
}
|
结果
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.6 MB,击败了83.59% 的Java用户
94. 二叉树的中序遍历
题目链接： 94. 二叉树的中序遍历
题目分析
递归遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
recur(root, result);
return result;
}
private void recur(TreeNode node, List<Integer> res) {
if (node == null) {
return;
}
recur(node.left, res);
res.add(node.val);
recur(node.right, res);
}
}
|
结果
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.6 MB,击败了83.37% 的Java用户
145. 二叉树的后序遍历
题目链接： 145. 二叉树的后序遍历
题目分析
递归遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
recur(root, result);
return result;
}
private void recur(TreeNode node, List<Integer> res) {
if (node == null) {
return;
}
recur(node.left, res);
recur(node.right, res);
res.add(node.val);
}
}
|
结果
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.6 MB,击败了84.32% 的Java用户
迭代遍历※
文章讲解： https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html
144. 二叉树的前序遍历
题目链接： 144. 二叉树的前序遍历
题目分析
迭代遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> deque = new ArrayDeque<>();
if (root != null)
deque.push(root);
while (!deque.isEmpty()) {
TreeNode pop = deque.pop();
result.add(pop.val);
if (pop.right != null) {
deque.push(pop.right);
}
if (pop.left != null) {
deque.push(pop.left);
}
}
return result;
}
}
|
结果
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.8 MB,击败了49.78% 的Java用户
94. 二叉树的中序遍历
题目链接： 94. 二叉树的中序遍历
题目分析
迭代遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Deque<TreeNode> deque = new ArrayDeque<>();
while (root != null || !deque.isEmpty()) {
if (root != null) {
deque.push(root);
root = root.left;
} else {
TreeNode pop = deque.pop();
result.add(pop.val);
root = pop.right;
}
}
return result;
}
}
|
结果
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.6 MB,击败了69.56% 的Java用户
145. 二叉树的后序遍历
题目链接： 145. 二叉树的后序遍历
题目分析
迭代遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> deque = new ArrayDeque<>();
if (root != null)
deque.push(root);
while (!deque.isEmpty()) {
TreeNode pop = deque.pop();
result.add(pop.val);
if (pop.left != null) {
deque.push(pop.left);
}
if (pop.right != null) {
deque.push(pop.right);
}
}
Collections.reverse(result);
return result;
}
}
|
结果
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.4 MB,击败了96.60% 的Java用户
统一迭代※
建议：这是统一迭代法的写法， 如果学有余力，可以掌握一下
文章讲解： https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html
144. 二叉树的前序遍历
题目链接： 144. 二叉树的前序遍历
题目分析
迭代遍历
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
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
TreeNode flag = new TreeNode();
Deque<TreeNode> deque = new ArrayDeque<>();
deque.push(root);
while (!deque.isEmpty()) {
TreeNode peek = deque.peek();
if (peek != flag) {
deque.pop();
if (peek.right != null)
deque.push(peek.right);
if (peek.left != null)
deque.push(peek.left);
deque.push(peek);
deque.push(flag);
} else {
deque.pop();
TreeNode pop = deque.pop();
result.add(pop.val);
}
}
return result;
}
}
|
结果
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.7 MB,击败了60.09% 的Java用户
94. 二叉树的中序遍历
题目链接： 94. 二叉树的中序遍历
题目分析
迭代遍历
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
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
TreeNode flag = new TreeNode();
Deque<TreeNode> deque = new ArrayDeque<>();
deque.push(root);
while (!deque.isEmpty()) {
TreeNode peek = deque.peek();
if (peek != flag) {
deque.pop();
if (peek.right != null)
deque.push(peek.right);
deque.push(peek);
deque.push(flag);
if (peek.left != null)
deque.push(peek.left);
} else {
deque.pop();
TreeNode pop = deque.pop();
result.add(pop.val);
}
}
return result;
}
}
|
结果
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.4 MB,击败了97.61% 的Java用户
145. 二叉树的后序遍历
题目链接： 145. 二叉树的后序遍历
题目分析
迭代遍历
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
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
TreeNode flag = new TreeNode();
Deque<TreeNode> deque = new ArrayDeque<>();
deque.push(root);
while (!deque.isEmpty()) {
TreeNode peek = deque.peek();
if (peek != flag) {
deque.pop();
deque.push(peek);
deque.push(flag);
if (peek.right != null)
deque.push(peek.right);
if (peek.left != null)
deque.push(peek.left);
} else {
deque.pop();
TreeNode pop = deque.pop();
result.add(pop.val);
}
}
return result;
}
}
|
结果
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.4 MB,击败了96.04% 的Java用户