当前位置:   article > 正文

Java 结合二叉树的层序遍历,来说明List嵌套(List<List<T>>)_jdk1.8list嵌套list嵌套list

jdk1.8list嵌套list嵌套list

有时候我们会遇到将 list 集合作为对象存入另一个 list 集合中,如List<List<Integer>>,对于像 List<List<T>> 这样的集合我们该如何定义、初始化、以及赋值和使用呢?

list嵌套定义、初始化以及赋值

错误定义

 List<List<Integer>> list = new List<List<Integer>>()//因为List是接口,不能实例化(Cannot instantiate the type List<List<Integer>>)

 List<List<Integer>> list = new LinkedList<LinkedList<Integer>>();
 //泛型的类型参数必须相同,会报cannot convert from  LinkedList<LinkedList<Integer>> to List<List<Integer>>
  • 1
  • 2
  • 3
  • 4
  • 5

正确定义

 //采用接口类(List) 引用 实现类(LinkedList)
 List<LinkedList<Integer>> list = new LinkedList<LinkedList<Integer>>();
 List<List<Integer>> list = new LinkedList<List<Integer>>();
 
 //不采用接口类  
 ArrayList<ArrayList<Integer>> list= new ArrayList<ArrayList<Integer>>();
 LinkedList<LinkedList<Integer>> list = new LinkedList<LinkedList<Integer>>();
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

上面所有定义中的 Integer 类型,也可以是 String 类型和其他类型

如何赋值

从里向外一层一层赋值就可以了

例如:

 //先定义嵌套List
 List<List<Integer>> list = new LinkedList<List<Integer>>()//在定义里层的 List 集合 
 List<Integer> arrayList = new ArrayList<>(); //内嵌List
 
 //
 list.add(0,arrayList); //为实现从底向上的层序遍历,将 list 每次都插入 list1 的头部
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

使用:结合二叉树的层序遍历来说明

题目描述:

给定一个二叉树,返回其节点值自底向上的层序遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

  • 输入:给定二叉树 [3,9,20,null,null,15,7]
  •              3
    
    • 1
  •           9     20
    
    • 1
  •              15     7
    
    • 1
  • 输出:返回其自底向上的层序遍历为:
  • [
  • [15,7],
  • [9,20],
  • [3]
  • ]

要求返回值是集合的嵌套形式输出

代码实现

  public List<List<Integer>> levelOrderTree(TreeNode root) {

      List<List<Integer>> list = new LinkedList<List<Integer>>();
      //ArrayList<ArrayList<Integer>> list1= new ArrayList<ArrayList<Integer>>();

      if( root == null){
          return list;
      }

      //使用队列实现层次遍历
      Queue<TreeNode> queue = new LinkedList<TreeNode>();
      queue.offer(root);

      while ( !queue.isEmpty() ){  //队列不为空
          List<Integer> arrayList = new ArrayList<>(); //内嵌List
          int size = queue.size();  // 必须单独定义,不能在 for循环中直接使用i < queue.size()

          for (int i = 0; i < size; i++){  //i < queue.size()时错误的,一次 for循环 size大小时固定的
              // 若是如 i < queue.size()可变的,则在一次 for中 left不为空时不能跳出 for循环
              TreeNode node = queue.poll(); //取出并删除队头的元素
              arrayList.add(node.data);

              TreeNode left = node.left;
              TreeNode right = node.right;

              if (left != null){
                  queue.offer(left); //根节点的左孩子入队
              }
              if (right != null){
                  queue.offer(right); //根节点的右孩子入队
              }
          }
          list.add(0,arrayList); //为实现从底向上的层序遍历,将 list 每次都插入 list1 的头部
      }

      return list;
  }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

结果

执行结果如下图所示,先输出叶子节点[15, 7],在输出次叶子节点[9, 20],最后输出根节点[3],这些都是作为单独对象存储在 list 集合中,实现 list 的嵌套使用。
在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/201868
推荐阅读
相关标签
  

闽ICP备14008679号