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

描述

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

样例

给一棵二叉树 {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;
  }
}

点评

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

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏互扯程序

activemq的高可用(zookeeper+leveldb)主从集群

ActiveMQ 是Apache出品,最流行的,能力强劲的开源消息总线。完全支持JMS1.1和J2EE 1.4规范的 JMS Provider实现

33630
来自专栏ChaMd5安全团队

OtterCTF 13道内存取证题目详细解析(下)

The reason that we took rick's PC memory dump is because there was a malware inf...

65750
来自专栏Spark学习技巧

面试|return 和finally那些事儿

try/catch/finally语句块的finally和return谁先执行呢?也即是我们在try内部调用return,然后finally内部又去修改retu...

13540
来自专栏编程坑太多

「小程序JAVA实战」swagger2的使用与接口测试(34)

import org.springframework.boot.SpringApplication; import org.springframework.bo...

19620
来自专栏zhisheng

Java微基准测试框架JMH

JMH,即Java Microbenchmark Harness,这是专门用于进行代码的微基准测试的一套工具API。

17930
来自专栏ChaMd5安全团队

OtterCTF 13道内存取证题目详细解析(中)

From a little research we found that the username of the logged on character is ...

27030
来自专栏ChaMd5安全团队

SWPUCTF 2018 WriteUp(上)

解题思路 先走了正常流程走了一下注册,登陆,输入邀请码,提交后被返回“不是有效的24位优惠码”,先尝试了一边base32加密,提交后返回“想骗我不是有效的优惠码...

32760
来自专栏微信公众号:Java团长

Java编程中,有哪些好的习惯从一开始就值得坚持?

来源:zhihu.com/question/32255673/answer/532272606

15640
来自专栏编程坑太多

「小程序JAVA实战」小程序登录与后端联调(36)

21010
来自专栏Spark学习技巧

爱奇艺的Java缓存之路,你应该知道的缓存进化史!

本文是上周去技术沙龙听了一下爱奇艺的Java缓存之路有感写出来的。先简单介绍一下爱奇艺的java缓存道路的发展吧。

44930

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励