Given a binary tree, return the level order traversal of its nodes‘ values. (ie, from left to right, level by level).
Given binary tree {3,9,20,#,#,15,7}
,
3 / 9 20 / 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
SOLUTION :
这个题有很多解法,包括用两个queue,一个queue+dummy node 以及只用一个queue的,这里就只说最优解,1 queue的了。
本题借鉴了大神的总结:http://www.1point3acres.com/bbs/thread-139294-1-1.html
基本上几个level order 的二叉树遍历都可以用这套思路。
思路:用queue去模拟层序遍历的过程,就是说要向queue中一层一层的输入,再输出,但是怎么保证输入的是同一层呢,我们用到一个变量,queue.size(),这个很关键,它保证了内层循环(负责向queue输入节点以及从queue拿出节点加入list中)执行次数就是这一层节点的个数。在实现时候的具体思想就是,拿出一个点,就把这个点的左右儿子加入到queue中,从任一一层二叉树来看,就是当这一层的所有点抖拿出来了之后,同时这些点的所有左右儿子也都加进去了。具体实现看代码:
注意事项,queue用LinkedList模拟,queue输入输出分别是add(),remove()。
public class Solution { /** * @param root: The root of binary tree. * @return: Level order a list of lists of integer */ public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (root == null){ return result; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (!queue.isEmpty()){ ArrayList<Integer> list = new ArrayList<Integer>(); int size = queue.size(); for (int i = 0; i < size; i++){ TreeNode cur = queue.remove(); if (cur.left != null){ queue.add(cur.left); } if (cur.right != null){ queue.add(cur.right); } list.add(cur.val); } result.add(new ArrayList<Integer>(list)); } return result; } }
[Lintcode] Binary Tree Level Order Traversal
原文:http://www.cnblogs.com/tritritri/p/4858504.html