首页 > 代码库 > Leetcode: Binary Tree Level Order Transversal
Leetcode: Binary Tree Level Order Transversal
Given a binary tree, return the level order traversal of its nodes‘ values. (ie, from left to right, level by level).For example:Given binary tree {3,9,20,#,#,15,7}, 3 / 9 20 / 15 7return its level order traversal as:[ [3], [9,20], [15,7]]
难度：78。其实思路很清楚，就是把树看成一个有向图，进行BFS。BST的通常做法都是维护一个队列。这道题的难度在于，如何在队列不断的入队出队操作中，确定哪些node是一个层次的。想了很久没什么好办法，参考了网上的做法，发现他在维护两个数：一个是父节点所在层次的节点在当前队列中的数目ParentNumInQ，另一个是子节点所在层次的节点在当前队列中的数目ChildNumInQ。初始数值为1和0. 每次父节点出队，ParentNumInQ--，每次子节点入队，ParentNumInQ++。一旦ParentNumInQ减至0，说明当前父节点层次已全部出队，全部被存入LinkedList中，这就得到了一层的所有节点。接下来需要一些更新，ParentNumInQ = ChildNumInQ, ChildNumInQ = 0开始考虑下一层。
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {12 ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>> ();13 if (root == null) return lists;14 LinkedList<TreeNode> queue = new LinkedList<TreeNode>();15 queue.add(root);16 int ParentNumInQ = 1;17 int ChildNumInQ = 0;18 ArrayList<Integer> list = new ArrayList<Integer>();19 while (!queue.isEmpty()) {20 TreeNode cur = queue.poll();21 list.add(cur.val);22 ParentNumInQ--;23 if (cur.left != null) {24 queue.add(cur.left);25 ChildNumInQ++;26 }27 if (cur.right != null) {28 queue.add(cur.right);29 ChildNumInQ++;30 }31 if (ParentNumInQ == 0) {32 ParentNumInQ = ChildNumInQ;33 ChildNumInQ = 0;34 lists.add(list);35 list = new ArrayList<Integer>();36 }37 }38 return lists;39 }40 }
Leetcode: Binary Tree Level Order Transversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。