第六章二叉树part01，递归法、迭代法实现二叉树遍历、层序遍历（借助队列数据结构）。
0. 理论基础
二叉树的种类
- 满二叉树
- 完全二叉树
- 二叉搜索树
- 平衡二叉搜索树
二叉树的存储方式
- 链式存储
- 数组存储（了解）
二叉树的遍历方式
- 深度优先遍历 （前/中/后序遍历）
- 广度优先遍历 （层序遍历）
二叉树的定义
1
2
3
4
5
6
7
8
9
10
11
12
| public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
|
递归算法的三要素
- 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。一般来说返回值为空，因为我们把返回值保存在一个参数数组里了。
- 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
- 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
1. 二叉树的递归遍历
1.1 解题过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
preOrder(root, res);
return res;
}
public void preOrder(TreeNode cur, List<Integer> res) {
if (cur == null) return;
res.add(cur.val);
preOrder(cur.left, res);
preOrder(cur.right, res);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inOrder(root, res);
return res;
}
public void inOrder(TreeNode cur, List<Integer> res) {
if(cur == null) return;
inOrder(cur.left, res);
res.add(cur.val);
inOrder(cur.right, res);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postOrder(root, res);
return res;
}
public void postOrder(TreeNode cur, List<Integer> res) {
if(cur == null) return;
postOrder(cur.left, res);
postOrder(cur.right, res);
res.add(cur.val);
}
}
|
2. 二叉树的迭代遍历
2.1 解题过程
- 前序遍历的过程借助一个栈实现，因为遍历的结点和要处理的结点（将结点值放入result数组）是一致的，只需注意栈是先进后出的，所以要让右孩子先入栈；
- 后序遍历的迭代法可以依据前序遍历reverse出来；
- 中序遍历，则额外需要借用一个cur指针的遍历来访问结点，栈用于处理结点上的元素。中序遍历迭代法，还需注意一下循环停止的条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
if (root != null) queue.offerFirst(root);
while(!queue.isEmpty()) {
TreeNode node = queue.pollFirst();
res.add(node.val);
if(node.right != null) queue.offerFirst(node.right);
if(node.left != null) queue.offerFirst(node.left);
}
return res;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
TreeNode cur = root;
while(cur != null || !queue.isEmpty()) {
if (cur != null) {
queue.offerFirst(cur);
cur = cur.left;
} else {
TreeNode node = queue.pollFirst();
res.add(node.val);
cur = node.right;
}
}
return res;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
if (root != null) queue.offerFirst(root);
while(!queue.isEmpty()) {
TreeNode node = queue.pollFirst();
res.add(node.val);
if(node.left != null) queue.offerFirst(node.left);
if(node.right != null) queue.offerFirst(node.right);
}
Collections.reverse(res);
return res;
}
}
|
3. 二叉树的层序遍历
3.1 解题过程
由于树结点无法直接访问到同一层的结点，因此需要借助一个队列来存储结点，并且注意每层弹出多少个元素，由一开始记录的size决定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
if(root != null) queue.offerLast(root);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> curLevel = new ArrayList<>();
while(size-- > 0) {
TreeNode node = queue.pollFirst();
curLevel.add(node.val);
if(node.left != null) queue.offerLast(node.left);
if(node.right != null) queue.offerLast(node.right);
}
res.add(curLevel);
}
return res;
}
}
|