文档章节

[LintCode] Binary Tree Level Order Traversal(二叉树的层次遍历)

honeymose
 honeymose
发布于 2018/12/17 12:26
字数 523
阅读 12
收藏 1

描述

给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问)

样例

给一棵二叉树 {3,9,20,#,#,15,7} :

  3
 / \
9  20
  /  \
 15   7

返回他的分层遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

挑战

挑战1:只使用一个队列去实现它

挑战2:用BFS算法来做

代码

GitHub 的源代码,请访问下面的链接:

https://github.com/cwiki-us/java-tutorial/blob/master/src/test/java/com/ossez/lang/tutorial/tests/lintcode/LintCode0069LevelOrderTest.java

 

package com.ossez.lang.tutorial.tests.lintcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.ossez.lang.tutorial.models.TreeNode;

/**
 * <p>
 * 69
 * <ul>
 * <li>@see <a href=
 * "https://www.cwiki.us/display/ITCLASSIFICATION/Binary+Tree+Level+Order+Traversal">https://www.cwiki.us/display/ITCLASSIFICATION/Binary+Tree+Level+Order+Traversal</a>
 * <li>@see<a href=
 * "https://www.lintcode.com/problem/binary-tree-level-order-traversal">https://www.lintcode.com/problem/binary-tree-level-order-traversal</a>
 * </ul>
 * </p>
 * 
 * @author YuCheng
 *
 */
public class LintCode0069LevelOrderTest {

  private final static Logger logger = LoggerFactory.getLogger(LintCode0069LevelOrderTest.class);

  /**
   * 
   */
  @Test
  public void testMain() {
    logger.debug("BEGIN");
    String data = "{3,9,20,#,#,15,7}";

    TreeNode tn = deserialize(data);
    System.out.println(levelOrder(tn));

  }

  /**
   * Deserialize from array to tree
   * 
   * @param data
   * @return
   */
  private TreeNode deserialize(String data) {
    // NULL CHECK
    if (data.equals("{}")) {
      return null;
    }

    ArrayList<TreeNode> treeList = new ArrayList<TreeNode>();

    data = data.replace("{", "");
    data = data.replace("}", "");
    String[] vals = data.split(",");

    // INSERT ROOT
    TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
    treeList.add(root);

    int index = 0;
    boolean isLeftChild = true;
    for (int i = 1; i < vals.length; i++) {
      if (!vals[i].equals("#")) {
        TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
        if (isLeftChild) {
          treeList.get(index).left = node;
        } else {
          treeList.get(index).right = node;
        }
        treeList.add(node);
      }

      // LEVEL
      if (!isLeftChild) {
        index++;
      }

      // MOVE TO RIGHT OR NEXT LEVEL
      isLeftChild = !isLeftChild;
    }

    return root;

  }

  private List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    List<List<Integer>> rs = new ArrayList<List<Integer>>();

    // NULL CHECK
    if (root == null) {
      return rs;
    }

    queue.offer(root);

    while (!queue.isEmpty()) {
      int length = queue.size();
      List<Integer> list = new ArrayList<Integer>();

      for (int i = 0; i < length; i++) {
        TreeNode curTN = queue.poll();
        list.add(curTN.val);
        if (curTN.left != null) {
          queue.offer(curTN.left);
        }
        if (curTN.right != null) {
          queue.offer(curTN.right);
        }
      }

      rs.add(list);
    }

    return rs;
  }
}

 

 

 

点评

这个程序可以使用队列的广度优先算法来进行遍历。

需要注意的是,因为在输出结果的时候需要按照层级来进行输出,那么需要考虑的一个算法就是二叉树的层级遍历算法。

这个算法要求在遍历的时候记录树的层级。

© 著作权归作者所有

共有 人打赏支持
honeymose
粉丝 4
博文 437
码字总数 200176
作品 0
东城
私信 提问
Leetcode 102. 二叉树的层次遍历

题目链接 https://leetcode.com/problems/binary-tree-level-order-traversal/description/ 题目描述 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例...

Gmxbb
2018/09/18
0
0
Leetcode 二叉树解题报告

1. Binary Tree Preorder Traversal Description Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 2 / 3 Output: [1,2,3] Analy......

BookThief
2018/07/29
0
0
PTA (Advanced Level)1020 Tree Traversals

Tree Traversals   Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output th......

suvvm
01/08
0
0
PAT 1020 Tree Traversals(根据二叉树中序后序遍历求层次遍历)

版权声明:转载请告知博主并要注明出处嗷~ https://blog.csdn.net/AkatsukiItachi/article/details/84502861 PAT1020 1020 Tree Traversals (25 分) Suppose that all the keys in a binar......

语海与冰
2018/11/25
0
0
二叉树层序遍历II

原题   Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).   For example:   ......

一贱书生
2016/12/21
6
0

没有更多内容

加载失败,请刷新页面

加载更多

Windows 上安装 Scala

在安装 Scala 之前需要先安装 Java 环境,具体安装的详细方法就不在这里描述了。 您可以自行搜索我们网站中的内容获得其他网站的帮助来获得如何安装 Java 环境的方法。 接下来,我们可以从 ...

honeymose
今天
1
0
数据库篇多表操作

第1章 多表操作 实际开发中,一个项目通常需要很多张表才能完成。例如:一个商城项目就需要分类表(category)、商品表(products)、订单表(orders)等多张表。且这些表的数据之间存在一定的关系...

stars永恒
今天
3
0
nginx日志自动切割

1.日志配置(Nginx 日志) access.log----记录哪些用户,哪些页面以及用户浏览器,IP等访问信息;error.log------记录服务器错误的日志 #配置日志存储路径:location / {      a...

em_aaron
昨天
5
0
java 反射

基本概念 RTTI,即Run-Time Type Identification,运行时类型识别。RTTI能在运行时就能够自动识别每个编译时已知的类型。   要想理解反射的原理,首先要了解什么是类型信息。Java让我们在运...

细节探索者
昨天
2
0
推荐转载连接

https://www.cnblogs.com/ysocean/p/7409779.html#_label0

小橙子的曼曼
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部