二叉树遍历中的前、中、后，说的都是双亲结点，而左孩子结点和右孩子结点始终是先左再右。基于递归实现二叉树的遍历算法较为简单，如果放弃递归策略而以非递归的方式实现，则所有的遍历实现都需要借助于 栈结构 。
前序遍历
前序遍历算法的遍历次序是 “中-左-右”。
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
this.doPreorderTraversal(root, res);
return res;
}
private void doPreorderTraversal(TreeNode node, List<Integer> res) {
if (null == node) {
return;
}
res.add(node.val);
this.doPreorderTraversal(node.left, res);
this.doPreorderTraversal(node.right, res);
}
|
非递归实现
前序遍历的非递归实现属于三种遍历中最简单的一种，因为双亲结点需要第一个被访问，所以依赖于栈，基本的算法流程如下：
- 根结点入栈；
- 出栈，访问该结点 N；
- 如果 N 的右孩子结点不为空，则入栈；
- 如果 N 的左孩子结点不为空，则入栈；
- 如果栈不为空，则返回步骤 2。
具体实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (null == root) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
final TreeNode node = stack.pop();
list.add(node.val);
if (null != node.right) {
stack.push(node.right);
}
if (null != node.left) {
stack.push(node.left);
}
}
return list;
}
|
由上述实现可以看出，整个算法流程需要注意的一点就是在将孩子结点入栈时需要先将右孩子结点入栈，再将左孩子结点入栈，从而保证左孩子结点先于右孩子结点被访问，以满足“中-左-右”的顺序约束。
中序遍历
中序遍历算法的遍历次序是 “左-中-右”。
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
this.doInorderTraversal(root, res);
return res;
}
public void doInorderTraversal(TreeNode node, List<Integer> res) {
if (null == node) {
return;
}
this.doInorderTraversal(node.left, res);
res.add(node.val);
this.doInorderTraversal(node.right, res);
}
|
非递归实现
假设有输入结点 N （初始时 N = root），中序遍历的非递归算法流程如下：
- 如果 N 不为 null 则入栈，然后赋值 N = N.left，循环直到 N 为 null 为止；
- 出栈，访问该结点 M；
- 如果 M 的右孩子结点为空则继续出栈，否则令 N 为 M 的右孩子结点，回到步骤 1。
具体实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (null != root || !stack.isEmpty()) {
while (root != null) {
stack.add(root);
root = root.left;
}
if (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
root = node.right;
}
}
return result;
}
|
后序遍历
后序遍历算法的遍历次序是 “左-右-中”。
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (null == root) {
return res;
}
this.doPostorderTraversal(root, res);
return res;
}
public void doPostorderTraversal(TreeNode node, List<Integer> res) {
if (null == node) {
return;
}
this.doPostorderTraversal(node.left, res);
this.doPostorderTraversal(node.right, res);
res.add(node.val);
}
|
非递归实现
后序遍历的非递归实现属于三种遍历中最复杂的一种，某一个结点被访问的条件需要满足以下两个条件之一：
- 该结点没有孩子结点；
- 该结点的孩子结点已经被访问过。
所以我们需要利用一个变量来记录上一次被访问的结点，令该变量为 pre，则算法思路如下：
- 根结点入栈；
- peek 栈顶元素，如果该结点满足上述两个条件之一，则 pop 栈顶元素并访问该结点，并记录到 pre 变量中；
- 如果不满足，则先判断如果右孩子不为空，则入栈，然后判断如果左孩子不为空，则入栈；
- 返回步骤 2，重复执行，直到栈为空为止。
具体实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if (null != root) stack.add(root);
TreeNode pre = null;
while (!stack.isEmpty()) {
TreeNode node = stack.peek();
if ((null == node.left && null == node.right)
|| (null != pre && (pre == node.right || pre == node.left))) {
stack.pop();
result.add(node.val);
pre = node;
} else {
if (null != node.right) stack.add(node.right);
if (null != node.left) stack.add(node.left);
}
}
return result;
}
|