您现在的位置是：首页 > 文章详情

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

日期：2018-12-16点击：330收藏

描述

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

样例

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