数据结构|二叉树的前序遍历、中序遍历和后序遍历

数据结构|二叉树的前序遍历、中序遍历和后序遍历

Scroll Down

0. 前言

在上一篇博客中,我总结了树的两种遍历策略,一个是深度优先遍历,一个是广度优先遍历。而在深度优先遍历中,根据访问节点的顺序不同,又可以分为三种遍历方法,分别是:

  • 前序遍历
  • 中序遍历
  • 后序遍历

今天就对上面三种遍历方式做个总结。

1. 定义

所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。

  • 前序遍历:
    • 先访问根节点,再访问左子节点,最后访问右子节点
    • 顺序:-左-右
  • 中序遍历:
    • 从根节点开始(注意不是先访问根节点),先访问左子节点,再访问根节点,最后访问右子节点
    • 顺序:左--右
  • 后序遍历:
    • 从根节点开始,先访问左子节点,再访问右子节点,最后访问根节点
    • 顺序:左-右-
      二叉树

对于上图中的树,三种不同的遍历方式的结果如下:

  • 前序遍历:ABDECFG
  • 中序遍历:DBEAFCG
  • 后序遍历:DEBFGCA

2. 三种遍历方式的递归实现

由于树是一种常见的递归形式的数据结构,因此使用递归的方式可以有效的解决树的问题。递归的优缺点此处不再赘述,可参考我的另一篇博客

2.1 前序遍历的递归实现

    //用于存放遍历后的结果
    private List<Integer> res = new LinkedList<>();

    //前序遍历(递归)
    public List<Integer> preOrderTravel(TreeNode root){
        if (root==null) return res;
        res.add(root.val);//记录根节点的值
        preOrderTravel(root.left);//递归遍历左子树
        preOrderTravel(root.right);//递归遍历右子树
        return res;
    }

先访问根节点,再递归访问根节点的左子树,最后递归访问根节点的右子树。

2.2 中序遍历的递归方式

    //用于存放遍历后的结果
    private List<Integer> res = new LinkedList<>();

    //中序遍历(递归)
    public List<Integer> inOrderTravel(TreeNode root){
        if (root==null) return res;
        preOrderTravel(root.left);//递归遍历左子树
        res.add(root.val);//记录根节点的值
        preOrderTravel(root.right);//递归遍历右子树
        return res;
    }

从根节点出发,先递归访问根节点的左子树,然后记录根节点的值,最后递归遍历根节点的右子树。

2.3 后序遍历的递归方式

    //用于存放遍历后的结果
    private List<Integer> res = new LinkedList<>();

    //后序遍历(递归)
    public List<Integer> postOrderTravel(TreeNode root){
        if (root==null) return res;
        preOrderTravel(root.left);//递归遍历左子树
        preOrderTravel(root.right);//递归遍历右子树
	res.add(root.val);//记录根节点的值
        return res;
    }

从根节点出发,先递归访问根节点的左子树,然后递归遍历根节点的右子树,最后记录根节点的值。

3. 三种遍历方式的非递归实现

递归的本质,就是由系统对函数在内存中进行压栈出栈,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。因此,非递归的方式去遍历树时,我们就要手动的来模拟这个过程。

3.1 前序遍历的非递归实现

对于上述二叉树,前序遍历的过程如下所示,首先记录根节点的值,再将右儿子加入栈中,最后将左儿子加入栈中。
深度优先
左儿子入栈之后,将左儿子出栈,然后重复上述过程。当栈为空时,表示所有的节点都访问过了,即遍历结束。
前序遍历的非递归实现具体如下:

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) return res;
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        //栈为空,表示所有节点访问完毕。
        while (!stack.isEmpty()){
            TreeNode treeNode = stack.pop();
            res.add(treeNode.val);//记录当前节点的值
            if (treeNode.right!=null){
                stack.add(treeNode.right);//当前节点的右儿子入栈
            }
            if (treeNode.left!=null){
                stack.add(treeNode.left);//当前节点的左儿子入栈
            }
        }
        return res;
    }

相关题目:Leetcode - 144.二叉树的前序遍历

3.2 中序遍历的非递归实现

中序遍历的过程如下图所示,此处借用leetcode用户王尼玛(这就是你拖更的原因??)的图演示一下,如有侵权,请联系删除。

中序遍历.gif

首先从根节点出发,沿着左子树的方向走,每到达一个节点,就将该节点存入栈中。
当走到左边的尽头后,从栈中弹出栈顶节点,并记录该节点的值,然后开始往右边走。

    public List<Integer> inorderTraversal1(TreeNode root){
        LinkedList<Integer> res = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty()||root!=null){
            //不断往左子树方向走,每走一次就将当前节点保存到栈中
            if (root!=null){
                stack.push(root);
                root = root.left;
            }
            else {
                //当前节点为空,说明左边走到头了,从栈中弹出节点并保存
                //然后转向右边节点,继续上面整个过程
                TreeNode treeNode = stack.pop();
                res.add(treeNode.val);
                root = treeNode.right;
            }
        }
        return res;
    }

上述实现存在一个缺点,即改变了二叉树的结构,因为每次访问节点都相当于在移动树的头指针。
相关题目:Leetcode - 94.二叉树的中序遍历

3.3 后序遍历的非递归实现

后序遍历的过程图此处就不再重复了,说一下遍历的思路:

由于后序遍历是最后访问根节点,因此,可以用一个临时变量来记录上一次访问的节点。首先从根节点出发,将根节点的左右儿子压入栈中。此时上一次访问的节点为空,说明当前节点的左右儿子还没有访问,继续将当前节点的左右儿子压入栈中,直到到达左子树的最深处。由于此时的节点没有左右儿子了,因此将节点出栈,并记录为已访问过的节点。在下一次循环中,将上次出栈的节点与当前节点比较,如果是当前节点的子节点,说明其左右节点均已访问,将当前结点出栈,更新pre记录的对象。

这样说着不太好理解,直接看代码吧。

public List<Integer> postorderTraversal1(TreeNode root){
        List<Integer> res = new LinkedList<>();//用于存放遍历的结果
        if (root == null) return res;
        LinkedList<TreeNode> stack = new LinkedList<>();//用Linkedlist模拟栈
        TreeNode pre = null;//用于记录上一次出栈的节点
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode curr = stack.peek();//检索但不出栈
            if ((curr.left==null&&curr.right==null)||(pre!=null&&(pre==curr.left||pre==curr.right))){
                pre = curr;
                res.add(curr.val);
                stack.poll();//出栈
            }
            else{
                if (curr.right!=null){
                    stack.push(curr.right);
                }
                if (curr.left!=null) {
                    stack.push(curr.left);
                }
            }
        }
        return res;

后序遍历的特点是:由于我们要最后访问根节点,因此,需要用一个临时变量来记录根节点的值。

相关题目:Leetcode - 145.二叉树的后序遍历

4. 其他实现(巧解)

上述的非递归的遍历只是常规解题的方法,既然有常规的,那也有不常规的解题方法。本文先总结如下几种方法(目前就遇到了这几种),以后遇到新颖的解题方法再记录下来。

4.1 后序遍历

由于前序遍历的访问顺序是:根-左-右,而后序遍历的访问顺序是:左-右-根。如果我们把前序遍历访问子节点的顺序改变一下:根-右-左,那将这个遍历结果反转过来,就是后序遍历的结果啦!

  • 前序遍历:根-左-右
  • 后序遍历:左-右-根
  • 交换前序遍历子节点访问顺序:根-右-左
  • 反转上述结果:左-右-根
    具体实现:
    public List<Integer> afterOrderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) return res;
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        //栈为空,表示所有节点访问完毕。
        while (!stack.isEmpty()){
            TreeNode treeNode = stack.pop();
            res.addFirst(treeNode.val);//头插法记录当前节点的值
            if (treeNode.right!=null){
                stack.add(treeNode.left);//当前节点的左儿子入栈
            }
            if (treeNode.left!=null){
                stack.add(treeNode.right);//当前节点的右儿子入栈
            }
        }
        return res;
    }

4.2 中序遍历

对于中序遍历,还有一种解法,叫做莫里斯遍历。说实话,第一次看到的时候,我心里想的就是卧槽还能这样?它的核心思想是,按照中序遍历的定义,将一棵二叉树转换为链表。再对这个链表进行遍历。其过程如下图所示。(此处借用leetcode用户王尼玛的图演示一下,如有侵权,请联系删除。)

莫里斯遍历.gif

详情请见Leetcode题解 - 莫里斯遍历

莫里斯遍历的具体实现如下:

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        TreeNode pre = null;
        while(root!=null) {
            //如果左节点不为空,就将当前节点连带右子树全部挂到
            //左节点的最右子树下面
            if(root.left!=null) {
                pre = root.left;
                while(pre.right!=null) {
                    pre = pre.right;
                }
                pre.right = root;
                //将root指向root的left
                TreeNode tmp = root;
                root = root.left;
                tmp.left = null;
                //左子树为空,则打印这个节点,并向右边遍历	
            } else {
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }

5. 总结

二叉树的遍历是二叉树中的一个重要问题。主要的方式分为递归和非递归。两种方式各有自己的优缺点,在实际生产中应该结合实际情况考虑。如果是面向面试学习,那么我建议这两种方式都应该掌握。

由于本人水平有限,非递归的代码写的不太优雅,希望能在今后的学习中总结出一套非递归的模板代码,便于自身的记忆。