二叉树遍历算法的非递归实现

二叉树遍历中的前、中、后,说的都是双亲节点,而左孩子节点和右孩子节点始终是先左再右。基于递归实现二叉树的遍历算法较为简单,如果放弃递归策略以非递归的方式实现,则所有的遍历的实现都需要 依赖于栈结构

一. 前序遍历

前序遍历算法的遍历次序是 “中-左-右”。

1.1 递归实现

1
2
3
4
5
6
7
8
9
10
11
12
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
this.recursion(root, result);
return result;
}

private void recursion(TreeNode node, List<Integer> list) {
if (null == node) return;
list.add(node.val);
if (null != node.left) this.recursion(node.left, list);
if (null != node.right) this.recursion(node.right, list);
}

1.2 非递归实现

先序遍历的非递归实现属于三种遍历中最简单的一种,因为双亲节点需要第一个被访问,所以依赖于栈,基本的算法流程是:

  1. 根结点入栈
  2. 出栈,访问该节点 N
  3. 如果 N 的右孩子节点不为空,则入栈
  4. 如果 N 的左孩子节点不为空,则入栈
  5. 如果栈不为空,则返回步骤 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 非递归(基于栈)
*
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if (null != root) stack.add(root); // 根节点入栈
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (null != node.right) stack.add(node.right); // 先右孩子节点入栈
if (null != node.left) stack.add(node.left); // 再左孩子节点入栈
}
return result;
}

二. 中序遍历

中序遍历算法的遍历次序是 “左-中-右”。

2.1 递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 中序遍历(基于递归)
*
* @param root
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
this.recursion(root, result);
return result;
}

/**
* 递归的方法
*
* @param node
* @param list
*/
public void recursion(TreeNode node, List<Integer> list) {
if (null == node) return;
if (null != node.left) this.recursion(node.left, list);
list.add(node.val);
if (null != node.right) this.recursion(node.right, list);
}

2.2 非递归实现

假设有输入节点 N (初始时 N = root),中序遍历非递归的思路如下:

  1. 如果 N != null,则入栈,然后 N = N.left,循环直到 N == null 为止
  2. 出栈,访问该节点 M
  3. 如果 M 的右孩子节点为空,则继续出栈,否则令 N 为 M 的右孩子节点,回到步骤 1
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
/**
* 中序遍历(基于栈)
*
* @param root
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
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
root = node.right;
}
}
return result;
}

三. 后序遍历

后序遍历算法的遍历次序是 “左-右-中”。

3.1 递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 后序遍历(基于递归)
*
* @param root
* @return
*/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
this.recursion(root, result);
return result;
}

private void recursion(TreeNode node, List<Integer> list) {
if (null == node) return;
if (null != node.left) this.recursion(node.left, list);
if (null != node.right) this.recursion(node.right, list);
list.add(node.val);
}

3.2 非递归实现

后序遍历的非递归实现属于三种遍历中最复杂的一种,某一个点被访问的条件是:

  1. 该节点没有孩子节点
  2. 该节点的孩子节点已经被访问过

所以我们需要利用一个变量来记录上一次被访问的节点,令该变量为 pre,则算法思路如下:

  1. 根结点入栈
  2. peek 栈顶元素,如果该节点满足上述两个条件之一,则 pop 栈顶元素并访问该节点,并记录到 pre 变量
  3. 如果 不满足,则先判断如果右孩子不为空,则入栈,然后判断如果左孩子不为空,则入栈
  4. 返回步骤 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
25
26
27
28
29
30
/**
* 后序遍历(基于栈)
*
* @param root
* @return
*/
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();
/*
* 1. 当前节点没有孩子节点
* 2. 当前节点的孩子节点是上次访问的节点
*/
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;
}

转载声明 : 版权所有,商业转载请联系作者,非商业转载请注明出处
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议
Powered by hexo & Theme by hiero   Copyright © 2015-2019 浙ICP备 16010916  号,指 · 间 All Rights Reserved.