经典算法 - 非递归遍历二叉树
一、前序遍历
思路
递归的时候是依赖于操作系统的递归栈来实现的，同样这里也可以定义一个栈来模拟：
- 遍历根结点
- 遍历根结点的左子树
- 遍历根结点的右子树
前序非递归遍历，想明白一个问题，根结点需要被访问几次？答案是两次，第一次遍历根结点一次了，第二次是遍历完它的左子树后，还得遍历它一次，才能遍历它的右子数！
所以，遍历完该结点后，就放入栈，弹栈后就可以再次得到上一个根结点，从而遍历到其右子数
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
pre(root, res);
return res;
}
private void pre(TreeNode root, List<Integer> res) {
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
res.add(root.val);
stack.add(root);
root = root.left;
}
root = stack.pop().right;
}
}
}
总结
加深对递归的理解，模拟题
二、中序遍历
思路
非递归中序遍历的写法基本跟非递归前序遍历差不多，顺序是：
- 遍历左子树
- 遍历根结点
- 遍历右子树
因此，可以发现，根结点的访问次数还是两次，第一次是左子树的根，第二次是需要访问该根的右子数，因此，还是用一个栈就可以做了
可以发现区别就是，在遍历完左子树，要遍历该左子树的右子树，才真正加入到结果集合
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inOrder(root, res);
return res;
}
private void inOrder(TreeNode root, List<Integer> res) {
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
res.add(stack.peek().val);
root = stack.pop().right;
}
}
}
总结
加深对中序遍历本质的理解，模拟题
三、后序遍历
思路
总体上还是用栈来实现，顺序是：
- 遍历左子树
- 遍历右子数
- 遍历根结点
可以发现，一个结点需要被访问三次，遍历结点的左子树、右子数、最后还要遍历它自己，一定得三次才能做到
所以这个跟前面两个遍历是不一样的
这里可以设定两个栈，一个存放结果，一个存放临时
- 结果栈，从底到头，存放的是根右左的结点序列，那么弹出来的时候，就是左右根的序列结点
- 临时栈，从底到头，依次存当前结点的左子树、右子树，那么每次遍历准备存放到结果栈的时候，右子树就会先遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
post(root, res);
return res;
}
private void post(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
// stack1 为临时栈，stack 2为结果栈
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
TreeNode cur = root;
stack1.push(cur);
while (!stack1.isEmpty()) {
cur = stack1.pop();
// 存放根结点
stack2.push(cur);
// 存放根结点的左子树
if (cur.left != null) {
stack1.push(cur.left);
}
// 遍历根结点的右子树
if (cur.right != null) {
stack1.push(cur.right);
}
}
// 左右根
while (!stack2.isEmpty()) {
res.add(stack2.pop().val);
}
}
}
总结
非递归后序遍历也不一定得两个栈，一个栈也可以做，不过略烧脑，久久刷一次，这次还是短时间想不出来，希望下一次能想出来，并且想法更好
四、层次遍历
思路
如果说前面两种是 DFS，那么层次遍历就是 BFS，而一般做 DFS 会需要使用栈，因为需要进行回溯，在 BFS 的时候，一般会需要使用到队列
二叉树层次遍历也是使用队列，写法也很多种，并不一定是下面的写法，下面的是为了方便理解，定义了两个队列，队列一存放当前层次的结点，队列二是辅助队列，存放下一层的结点，在当前层的结点遍历完后，就交换引用，可以继续遍历下一层的结点
class Solution {
Queue<TreeNode> qTravers = new LinkedList<>();
Queue<TreeNode> qHelp = new LinkedList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
qTravers.offer(root);
while (!qTravers.isEmpty()) {
List<Integer> level = new ArrayList<>();
while (!qTravers.isEmpty()) {
TreeNode cur = qTravers.poll();
level.add(cur.val);
if (cur.left != null) {
qHelp.offer(cur.left);
}
if (cur.right != null) {
qHelp.offer(cur.right);
}
}
res.add(level);
swapUpdate();
}
return res;
}
private void swapUpdate() {
Queue<TreeNode> temp = qTravers;
qTravers = qHelp;
qHelp = temp;
}
}
总结
复习 BFS ，下回应该玩玩迷宫 BFS / DFS 试试了