浅谈二叉树遍历

这里就对二叉树的遍历方式进行总结

abstract.png

基于递归的遍历

前序遍历

前序遍历:即对二叉树按照当前节点、左子树、右子树的顺序进行遍历。显然借助递归,非常容易实现、理解

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
/**
* 基于递归的前序遍历
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
dfs(root, list);
return list;
}

private void dfs(TreeNode cur, List<Integer> list) {
if( cur==null ) {
return;
}

// 1. 处理当前节点
list.add( cur.val );

// 2. 处理左子树
dfs(cur.left, list);

// 3. 处理右子树
dfs(cur.right, list);
}
}

中序遍历

中序遍历:即对二叉树按照左子树、当前节点、右子树的顺序进行遍历。显然借助递归,非常容易实现、理解

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
/**
* 基于递归的中序遍历
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
dfs(root, list);
return list;
}

private void dfs(TreeNode cur, List<Integer> list) {
if( cur==null ) {
return;
}

// 1. 处理左子树
dfs(cur.left, list);

// 2. 处理当前节点
list.add( cur.val );

// 3. 处理右子树
dfs(cur.right, list);
}
}

后序遍历

后序遍历:即对二叉树按照左子树、右子树、当前节点的顺序进行遍历。显然借助递归,非常容易实现、理解

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
/**
* 基于递归的后序遍历
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
dfs(root, list);
return list;
}

private void dfs(TreeNode cur, List<Integer> list) {
if( cur==null ) {
return;
}

// 1. 处理左子树
dfs(cur.left, list);

// 2. 处理右子树
dfs(cur.right, list);

// 3. 处理当前节点
list.add( cur.val );
}
}

基于迭代的遍历

前序遍历

不同于递归隐式维护栈的便捷,在通过迭代进行遍历时需要我们显式地维护一个栈。具体地,在前序遍历当中。首先需要处理对当前节点进行处理、然后沿着左子树一直入栈。当左子树遍历完毕, 通过出栈获取父节点来对右子树再进行处理

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
/**
* 基于迭代的前序遍历
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
LinkedList<TreeNode> stack = new LinkedList<>();

while ( root!=null || !stack.isEmpty() ) {
while (root!=null) {
// 先处理当前节点
res.add( root.val );
// 然后沿左子树一直入栈
stack.addLast( root );
root = root.left;
}

// 左子树遍历完毕, 通过父节点来对右子树再进行处理
TreeNode parent = stack.removeLast();
root = parent.right;
}

return res;
}
}

中序遍历

不同于递归隐式维护栈的便捷,在通过迭代进行遍历时需要我们显式地维护一个栈。具体地,在中序遍历当中。首先沿着左子树一直入栈。当左子树遍历完毕, 通过出栈获取父节点并对其进行处理,最后对右子树再进行处理

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

/**
* 基于迭代的中序遍历
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
LinkedList<TreeNode> stack = new LinkedList<>();

while ( root!=null || !stack.isEmpty() ) {
while ( root!=null ) {
// 先沿左子树一直入栈
stack.addLast( root );
root = root.left;
}

// 左子树遍历完毕, 获取父节点
TreeNode parent = stack.removeLast();
// 处理父节点的值
res.add( parent.val );
// 通过父节点对右子树再进行处理
root = parent.right;
}

return res;
}
}

后序遍历

后序遍历的顺序是左、右、当前。如果直接使用栈按这个顺序进行遍历输出会比较麻烦。故我们可以先按照当前、右、左的顺序进行迭代遍历,显然这个过程与前序遍历非常类似,只是需要把代码中涉及左、右子树的调换下即可。最后对遍历结果进行翻转。这样遍历结果就由当前、右、左 就变为 左、右、当前。即我们所需的后序遍历结果

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<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
LinkedList<TreeNode> stack = new LinkedList<>();

// 先按 根、右、左 的顺序进行遍历
while ( root!=null || !stack.isEmpty() ) {
while (root!=null) {
// 先处理当前节点
res.add( root.val );
// 然后沿右子树一直入栈
stack.addLast( root );
root = root.right;
}

// 右子树遍历完毕, 通过父节点获取左子树再进行处理
TreeNode parent = stack.removeLast();
root = parent.left;
}

// 对遍历结果进行翻转
// 这样遍历结果就由 根、右、左 就变为 左、右、根, 即后序遍历
Collections.reverse( res );
return res;
}
}

层序遍历

对于二叉树的层序遍历就简单很多了。我们借助队列的FIFO特性即可轻松实现

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
class Solution {
public List<Integer> levelOrder(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}

Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);

while ( !queue.isEmpty() ) {
// 弹出队首元素, 进行处理
TreeNode cur = queue.poll();
res.add( node.val );

// 将当前节点的左、右子节点加入队列
if( node.left != null ) {
queue.add( node.left );
}
if( node.right != null ) {
queue.add( node.right );
}
}

return res;
}
}

基于Morris算法的遍历

基本原理

Morris算法为二叉树的遍历提供了新的思路,其通过充分利用树中叶子节点存在大量空指针这一特点。实现了常数级别的空间复杂度。在进一步介绍该算法之前,我们先来说明一个概念——mostRight节点。其用于表示当前节点cur的左子树的最右节点。例如下图的一个二叉树。如果当前节点为1,则mostRight节点即为5;如果当前节点为3,则mostRight节点即为6

figure 1.jpeg

实际上,Morris算法非常简单。其基本遍历流程如下:

  1. 将当前节点cur初始化为root
  2. 当前节点cur如果不存在左子树。则将当前节点指向其右子树,以便遍历当前节点的右子树
  3. 当前节点cur如果存在左子树,则先获取cur节点的mostRight节点
    • 如果mostRight节点的右子节点为空,此时说明cur节点的左子树还未遍历。故:一方面,我们将mostRight节点的右子节点设置为cur节点;另一方面,将当前节点指向其左子树,以便遍历当前节点的左子树
    • 如果mostRight节点的右子节点为当前节点cur,此时说明cur节点的左子树已经遍历完成。故:一方面,我们将mostRight节点的右子节点设置为null空指针;另一方面,将当前节点指向其右子树,以便遍历当前节点的右子树
  4. 重复Step 2、Step 3,直到当前节点cur为null时为止

该算法遍历过程的示意图如下,可以看到当一个节点的左子树未遍历完时,Morris算法会利用原叶子节点的null空指针修改树。而当该节点的左子树遍历后,会把对树的修改进行撤回。以恢复树原有的结构

figure 2.jpeg

前序遍历

这里基于Morris算法来实现前序遍历。问题的关键就在于何时对当前节点进行处理。显然这里有两个时机,一方面,遍历过程中发现当前节点的左子树为空。则在对当前节点的右子树进行遍历前,需要对当前节点进行处理;另一方面,遍历过程中发现当前节点的左子树不为空,则在对当前节点的左子树进行遍历前,需要对当前节点进行处理

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
38
39
40
41
42
43
44
45
/**
* 基于Morris算法的前序遍历
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if( root == null ) {
return res;
}

TreeNode cur = root;
// 当前节点cur的左子树的最右节点
TreeNode mostRight = null;

while ( cur != null ) {
// 当前节点的左子树为空
if( cur.left == null ) {
// 处理当前节点
res.add( cur.val );
// 处理当前节点的右子树
cur = cur.right;
} else { // 当前节点的左子树不为空
// 寻找当前节点cur的左子树的最右节点
mostRight = cur.left;
while ( mostRight.right!=null && mostRight.right!=cur ) {
mostRight = mostRight.right;
}

if( mostRight.right == null) { // 说明cur节点的左子树未遍历
// 处理当前节点
res.add( cur.val );
// 处理当前节点的左子树
mostRight.right = cur;
cur = cur.left;
} else if ( mostRight.right == cur ) { // 说明cur节点的左子树已经遍历完成
// 处理当前节点的右子树
mostRight.right = null;
cur = cur.right;
}
}
}

return res;
}
}

中序遍历

这里基于Morris算法来实现中序遍历。问题的关键就在于何时对当前节点进行处理。显然这里有两个时机,一方面,遍历过程中发现当前节点的左子树为空。则在对当前节点的右子树进行遍历前,需要对当前节点进行处理;另一方面,遍历过程中发现当前节点的左子树不为空,则在对当前节点的左子树完成遍历后,需要对当前节点进行处理

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
38
39
40
41
42
43
44
45
/**
* 基于Morris算法的中序遍历
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if( root == null ) {
return res;
}

TreeNode cur = root;
// 当前节点cur的左子树的最右节点
TreeNode mostRight = null;

while ( cur != null ) {
// 当前节点的左子树为空
if( cur.left == null ) {
// 处理当前节点
res.add( cur.val );
// 处理当前节点的右子树
cur = cur.right;
} else { // 当前节点的左子树不为空
// 寻找当前节点cur的左子树的最右节点
mostRight = cur.left;
while ( mostRight.right!=null && mostRight.right!=cur ) {
mostRight = mostRight.right;
}

if( mostRight.right == null) { // 说明cur节点的左子树未遍历
// 处理当前节点的左子树
mostRight.right = cur;
cur = cur.left;
} else if ( mostRight.right == cur ) { // 说明cur节点的左子树已经遍历完成
// 处理当前节点
res.add( cur.val );
// 处理当前节点的右子树
mostRight.right = null;
cur = cur.right;
}
}
}

return res;
}
}

Note

这里给出本文中关于树节点的类定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 树的节点
*/
class TreeNode {
TreeNode left;

TreeNode right;

int val;

TreeNode() {
}

TreeNode(int val) {
this.val = val;
}

TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
0%