欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树(一)树的遍历

程序员文章站 2022-03-14 17:48:55
...

树的遍历

近期参加复旦互联网协会的刷题营,所以我勉勉强强又开始做题啦。现在变得更务实啦,要想提升能力,超过别人就是要依靠一项项的指标的胜利,这样的评价是更加客观的。想要提升能力,一方面要靠平时的积累,另外一方面也要依靠瓶颈期的奋力一搏。当然,我的意思是更加侧重前者的。话不多说啦,开始今天的话题——树的遍历。如果用递归的方法是非常简单,也是非常推荐的。但是,用迭代的方法也不难!!!所以我决定在这里探讨一下。
 

LeetCode题目

中序遍历 ,前序遍历 和 后序遍历 。当然,我知道有的朋友,就是喜欢野蛮自己的体魄,那你可以试一试,从中序与后序遍历序列构造二叉树 , 从前序与中序遍历序列构造二叉树 以及 根据前序和后序遍历构造二叉树。 保证你可以受到全身心的虐待。

各种遍历——递归实现

有基础的同学,跳过本节。

首先是TreeNode结构。

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

三种遍历的区别在于,什么时候访问root的值。下面是中序遍历,返回按序排序的值。

class Solution {
    List<Integer> list = new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        add(root);
        return list;
    }

    private void add(TreeNode root) {
        if (root == null) return;
        add(root.left);
        list.add(root.val);
        add(root.right);
    }
}

之后,是前序遍历,先访问root父节点。此后,再访问左子树。

class Solution {
    List<Integer> list = new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        add(root);
        return list;
    }

    private void add(TreeNode root) {
        if (root == null) return;
        list.add(root.val);
        add(root.left);
        add(root.right);
    }
}

后序遍历也很简单,就是最后访问父节点。

class Solution {
    List<Integer> list = new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        add(root);
        return list;
    }

    private void add(TreeNode root) {
        if (root == null) return;
        add(root.left);
        add(root.right);
        list.add(root.val);
    }
}

各种遍历的原理图

相信阅读了上面的内容,大家都产生了一种树的遍历很简单的错觉。然而,真实的情况是确实不难。哈哈,接下来讲重点啦!

首先是中序遍历的遍历顺序图。引用LeetCode的说法,Left -> Node -> Right。只有先访问完左子树,才能返回访问中间节点的元素,再访问右子树。顺序按照1,2,3,4,...,7

树(一)树的遍历

接下来,大家一定好奇前序遍历的图。从1开始,到15. 增加箭头,也许会更加清楚一点,按照LeetCode的说法,Top -> Bottom, Left -> Right。

树(一)树的遍历

然后,是后序遍历。同样是从1开始。加上标线之后,或许更加清楚。按照LeetCode的说法,Bottom -> Top, Left -> Right。

 

树(一)树的遍历

各种遍历——迭代实现

中序遍历

主要通过Stack实现。

树(一)树的遍历

前序遍历

还是和之前的代码一样,只不过访问元素的顺序变了。

树(一)树的遍历

后序遍历

同样用Stack,但是,List用LinkedList,添加的时候用addFirst方法。
树(一)树的遍历

后序遍历,在将中序表达式,转化为逆波兰式的时候可以派上用场。

先序遍历,可以在列出目录中的所有文件的时候使用——先列出当前文件夹的所有文件。
关于各种遍历的用途,参考了这篇文章: https://blog.csdn.net/qq_31929931/article/details/77255658