二叉树遍历

题目

给定一个二叉树,返回它的中序 遍历。

示例: 输入: [1,null,2,3] 1 2 / 3

输出: [1,3,2]

解答

第一种、递归遍历
public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> nodes = new ArrayList<>();
        return helper(root, nodes);
    }

    public static List<Integer> helper(TreeNode treeNode, List<Integer> list) {
        if (treeNode != null) {
            if (treeNode.left != null){
                helper(treeNode.left,list);
            }
            list.add(treeNode.val);
            if (treeNode.right != null){
                helper(treeNode.right,list);
            }
        }
        return list;
    }

第二种、使用栈的方式
 public static List<Integer> inorder(TreeNode treeNode, List<Integer> list) {
        Stack<TreeNode> stack = new Stack<>();

        TreeNode curr = treeNode;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            list.add(curr.val);

            curr = curr.right;
        }
        return list;
    }

解析

1、使用递归的方式简单暴力 2、

  • 中序 :左 -> 根 -> 右
  • 前序 :根 -> 左 -> 右
  • 后序 :左 -> 右 -> 根

遍历树,总是从根开始,而中序需要左,这种结构使用栈的方式存储,右节点依次遍历。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 布隆过滤器

      布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个...

    OPice
  • 车(ju)一步吃卒

    题目: 在一个 8 x 8 的棋盘上,有一个白色车(rook)。也可能有空方块,白色的象(bishop)和黑色的卒(pawn)。它们分别以字符 “R”,“.”...

    OPice
  • 工厂模式

    工厂模式属于创建对象模式,提供给客户端共同创建对象的接口,不暴露创建对象的逻辑。 统一生产对象,便于管理和解耦。 例如:想要一辆汽车,直接去4s店提货,而不...

    OPice
  • Java 中的 Optional

    从 Java 8 引入的一个很有趣的特性是 Optional 类。Optional 类主要解决的问题是臭名昭著的空指针异常(NullPointerExcept...

    java乐园
  • PHP7.1新特性

    参数以及返回值的类型现在可以通过在类型前加上一个问号使之允许为空。当启用这个特性时,传入的参数或者函数返回的结果要么是给定的类型,要么是null

    ITer.996
  • 在CentOS8下安装Python3和ansible

    在CentOS7中,可以直接通过yum安装ansible。但是CentOS8的默认yum源下已不再提供ansible的安装包了,转而需要通过Python的pip...

    端碗吹水
  • 蓝桥杯 基础练习 回形取数

      回形取数就是沿矩阵的边取数,若当前方向上无数可取或已经取过,则左转90度。一开始位于矩阵左上角,方向向下。输入格式  输入第一行是两个不超过200的正整数m...

    Debug客栈
  • JS实现OO机制

    一、简单原型机制介绍 继承是OO语言的标配,基本所有的语言都有继承的功能,使用继承方便对象的一些属性和方法的共享,Javascript也从其他OO语言上借鉴了这...

    郑小超.
  • 用数据全面解读新型冠状病毒疫情趋势

    花了一天的时间做了个浙江省疫情的数据分析仪表盘,我们就根据这个数据仪表盘来对浙江的疫情做个大概的解读。

    王佩军
  • 面试被问:5 亿整数的大文件,排个序 ?

    给你1个文件bigdata,大小4663M,5亿个数,文件中的数据随机,如下一行一个整数:

    田维常

扫码关注云+社区

领取腾讯云代金券