二叉树有多种遍历方法，例如深度优先遍历，广度优先遍历，层次遍历等，本文将对这些遍历方式进行归纳。
所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有结点的访问称为遍历(traversal)。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历，深度优先一般用递归或堆栈，广度优先一般用队列。
我们对二叉树的结点做出如下所示的定义：
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.先序遍历，即根左右，先遍历根结点，再依次遍历左结点，右结点。
- 2.中序遍历，即左根右，先遍历左结点，再依次遍历根结点，右结点。
- 3.后序遍历，即左右根，先依次遍历左结点，右结点，最后再遍历根结点。
若使用先序遍历，手动得到的结果为：57842913；若使用中序遍历，得到的结果为：87245913；若使用后序遍历，得到的结果为：82473195。
每一种深度优先遍历方案都有使用显式栈的非递归算法和递归算法。
LeetCode上有关于深度优先遍历的题目，分别是：
- 144.二叉树的前序遍历
- 145.二叉树的后序遍历
- 94.二叉树的中序遍历
递归思路
先序遍历
递归思路都很简单，即使用递归的方式，依次访问根结点，左结点，右结点。其他的递归方法也与此基本相似。
递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
所有的递归算法，都要按照三要素来书写：
1.确定递归函数的参数与返回值
即：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2.确定边界条件
即：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3.确定递归的逻辑
即：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
以当前的先序遍历为例：
1.确定递归函数的参数与返回值: 本题需要将所有的数据存入ArrayList中，因此并不需要返回值，返回值即void，需要的参数即为根结点的值TreeNode cur和List list。代码为private void preorder(TreeNode cur, List list)
2.确定边界条件: 边界条件即为若当前遍历的结点值为空，则直接return终止递归。if (cur == NULL) return;
3.确定递归的逻辑: 递归的逻辑即先访问根结点，再访问左结点，再访问右结点。因此调用的代码如下所示：
1
2
3
| list.add(cur.val);
preorder(cur.left, list);
preorder(cur.right, list);
|
递归算法的时间复杂度为：O(n)，空间复杂度为：O(n)，代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
preorder(root, list);
return list;
}
private void preorder(TreeNode cur, List list) {
if(cur == null) {
return;
}
list.add(cur.val);
preorder(cur.left, list);
preorder(cur.right, list);
}
}
|
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
preorder(root, list);
return list;
}
private void preorder(TreeNode cur, List list) {
if(cur == null) {
return;
}
preorder(cur.left, list);
list.add(cur.val);
preorder(cur.right, list);
}
}
|
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
preorder(root, list);
return list;
}
private void preorder(TreeNode cur, List list) {
if(cur == null) {
return;
}
preorder(cur.left, list);
preorder(cur.right, list);
list.add(cur.val);
}
}
|
非递归思路
以先序遍历为例：因为要在遍历完结点的左子树后接着遍历结点的右子树，为了能找到该结点，需要使用栈来进行暂存。中序和后序也都涉及到回溯，所以都需要用到栈。因此需要手动维护一个栈用来进行数据的暂存。
先序遍历
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> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while(!stack.empty() || root != null) {
while(root != null) {
list.add(root.val);
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;
}
return list;
}
}
|
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<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode temp = stack.pop();
if(temp == null) continue;
result.add(temp.val);
stack.push(temp.right);
stack.push(temp.left);
}
return result;
}
}
|
中序遍历
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> List = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while(!stack.empty() || root != null) {
while(root != null) {
stack.push(root);
root = root.left;
}
list.add(root.val);
root = stack.pop();
root = root.right;
}
}
}
|
后序遍历
思路一：
思路一则是后序遍历在决定是否可以访问当前结点的值的时候，需要考虑其左右子树是否都已经遍历完成。所以需要设置一个lastVisited标记。若lastVisited等于当前考查结点的右子树(说明右侧子树已经遍历完成)，或者当前表示该结点的左右子树都已经遍历完成，则可以访问当前结点。
因此可以使用如下代码进行后序遍历：
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> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode lastVisited = root;
while(!stack.empty() || root != null) {
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.peek();
if(root.right == null || root.right == lastVisited){
list.add(root.val);
root = stack.pop();
lastVisited = root;
root = null;
} else {
root = root.right;
}
}
return list;
}
}
|
思路二：
思路二算是一种简单的奇技淫巧，本质上并不算是后序遍历。我们可以思考：先序遍历是根左右我们可以调整代码的顺序使其很容易变成根右左反转list数组可以使得顺序变为左右根，我们发现此时再进行了两次简单的修改之后，由前序遍历变成了后序遍历。此时我们希望向List的头插入元素实现反转的操作，所以我们使用LinkedList可以有较好的时间性能。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
while(!stack.empty() || root != null) {
while(root != null) {
stack.push(root);
list.add(0, root.val);
root = root.right;
}
root = stack.pop();
root = root.left;
}
return list;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> result = new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode temp = stack.pop();
if(temp == null) continue;
stack.push(temp.left);
stack.push(temp.right);
result.add(0, temp.val);
}
return result;
}
}
|
此方法的时间性能略逊于后序遍历的一般解法。使用思路一在LeetCode中提交击败100% Java提交，此方法击败49.89%提交。
至此所有的非递归算法都保证了格式上的基本统一，方便记忆以及面试时的书写。
二叉树的广度优先遍历
在进行深度优先遍历的时候，我们知道了应该使用数据结构栈。那么如何进行广度优先遍历呢，我们可以使用队列这一数据结构。思路如下，首先根结点若不为空，则将根结点放入队列中，每次循环取出队列中的队首元素，将队首元素进行暂存，判断是否可以将该队首节点的左结点右结点入队列(不为null)，并进行计数。当前计数递减为0时，说明一层已经遍历完毕，可以对下一层进行遍历。依次进行相关操作，最终可以得到层序遍历的结果。
LeetCode题目 102.二叉树的层序遍历
给你一个二叉树，请你返回其按层序遍历得到的节点值。(即逐层地，从左到右访问所有节点)。
例如[3,9,20,null,null,15,7]，应返回[ [3], [9,20], [15,7] ]
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
| class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> list = new ArrayList<List<Integer>>();
if(root == null) return list;
int count = 1;
queue.offer(root);
while(!queue.isEmpty()) {
int temp = 0;
List<Integer> row = new ArrayList<>();
while(count > 0){
root = queue.poll();
row.add(root.val);
if(root.left != null) {
temp++;
queue.offer(root.left);
}
if(root.right != null) {
temp++;
queue.offer(root.right);
}
count--;
}
count = temp;
list.add(row);
}
return list;
}
}
|
