剑指offer4J【特别篇】树的前序、中序、后续、层序遍历 非递
2020-11-25 本文已影响0人
sxqiong
树的花式遍历需要烂熟于心。递归方式想必已经信手拈来。，大部分树类型的算法题都离不开4种遍历。有很多基础遍历的变种，今天我们就一起理解下，树的非递归的遍历方式。
树结构
可爱的小树
前序遍历
前序遍历 跟-左-右的顺序，上述例子的遍历结果即：[3,9,20,15,7]，非递归方式我们该如何思考呢？这里我们可以使用栈结构，模拟递归的过程。
- 输出
- 把根放进栈里，方便我们后续找右节点。
- 把左节点当成根进行下一轮循环
- 当左节点为空时候，尝试出栈上一个根节点
- 把右节点当成根进行下一轮循环
- 当栈空了 当前节点也空了时候 结束循环
翻译成代码
public static List preOrder(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> stack = new LinkedList<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
res.add(root.getValue());
stack.push(root);
root = root.getLeft();
} else {
root = stack.pop().getRight();
}
}
return res;
}
中序遍历
中序遍历 左-跟-右的顺序，上述例子的遍历结果即：[9,3,15,20,7]，这里我们依旧可以使用栈结构，模拟递归的过程
- 根入栈
- 把左节点当成根进行下一轮循环
- 当左节点为空时候，尝试出栈上一个根节点
- 输出
- 把右节点当成根进行下一轮循环
- 当栈空了 当前节点也空了时候 结束循环
中序跟前序差别是，中序先在节点出栈时进行输出，出栈即表示所有的左已经入栈了
翻译成代码
public static List<Integer> inOrder(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> stack = new LinkedList<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
root = root.getLeft();
} else {
root = stack.pop();
res.add(root.getValue());
root = root.getRight();
}
}
return res;
}
后序遍历
后序遍历稍微麻烦一点， 左-右-根，这里我们依旧使用栈来实现
- 根先入栈
- 当栈内不为空时，我们进行循环
- 我们先把当前元素置为栈内第一个元素
- 如果当前元素没左孩子也没右孩子则输出
- 如果当前元素的左孩子、右孩子都输出完了，那自己输出
- 否则入栈右孩子，入栈左孩子
- 继续循环
那怎么判断左、右是不是已经输出完毕？
这里我们可以考虑下 一个节点有哪些状态
-
case1
-
case2
-
case3
-
case4
case4 在条件如果当前元素没左孩子也没右孩子则输出种已经输出了，我们要考虑的只有前三个case：
- case1：当左，右已经遍历则输出根，即上一个遍历的节点是右节点时候，输出根
- case2: 当右节点已经遍历则输出根，即上一个遍历的节点是右节点时候，输出根
- case3: 当左节点已经遍历则输出根，即上一个遍历的节点是左节点时候，输出根
所以，我们只需要存一个前置遍历节点，当前置遍历节点满足上述case时候即可输出根，即 当前序是当前节点的左或者右时候，即可输出根。
翻译成代码：
public static List<Integer> aftOrder(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
TreeNode cur = null, pre = new TreeNode(-1);
while (!stack.isEmpty()) {
cur = stack.peek();
if ((cur.getLeft() == null && cur.getRight() == null)
|| pre == cur.getLeft()
|| pre == cur.getRight()) {
res.add(cur.getValue());
pre = stack.pop();
} else {
if (cur.getRight() != null)
stack.push(cur.getRight());
if (cur.getLeft() != null)
stack.push(cur.getLeft());
}
}
return res;
}
这里需要注意个细节，pre的初始值不要设置为null,否则第一次遍历时候，如果当前节点不存在左或者右 就会存在问题。
层序遍历
层序遍历相比另外三种，比较简单，我们只要用队列实现即可
- 先出队列，输出
- 左入队列
- 右入队列
- 继续循环
public static List<Integer> floorOrder(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
res.add(cur.getValue());
if (cur.getLeft() != null) queue.add(cur.getLeft());
if (cur.getRight() != null) queue.add(cur.getRight());
}
return res;
}
但层序遍历有很多变种，比如：每一层单独一个数组，输出每层数组的集合、Z字打印每一层等
这类我们只要在上述出栈前记录下栈内元素个数，即当前层的数量，再去按数量处理即可
例子：
public static List<List<Integer>> floorOrderWithFloor(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> data = new ArrayList<>();
while (size-->0){
TreeNode cur = queue.poll();
data.add(cur.getValue());
if (cur.getLeft() != null) queue.add(cur.getLeft());
if (cur.getRight() != null) queue.add(cur.getRight());
}
res.add(data);
}
return res;
}
happy ending~
源码: 剑指offer4J
