Question:
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 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
Analysis:
问题描述：给出一棵二叉树，返回它的节点的层次遍历。
思路：二叉树的层次遍历要用到队列。每次访问一个节点时，该节点出队列，同时它的左右节点分别入队。但是这个题目要求我们将每个层次上的节点分开，因此要额外使用一个指针指向下一层的初始节点（即本层节点在下层初始节点开始前结束）。
1）遍历每一层的节点时，终止条件就是当前节点是否等于下一层的起始节点。
2）整个循环的终止是判断队列是否为空了。
Answer：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<List<Integer>>(); List<Integer> l = new ArrayList<Integer>(); if(root == null) return res; if(root.left == null && root.right == null) { l.add(root.val); res.add(l); return res; } TreeNode start; //记录了每一层的开始 Queue<TreeNode> node = new LinkedList<TreeNode>(); node.offer(root); while(!node.isEmpty()) { TreeNode cur = node.peek(); List<Integer> thisLevel = new ArrayList<Integer>(); start = null; while(node.peek() != start && !node.isEmpty()) { cur = node.poll(); if(start == null) { if(cur.left != null) start = cur.left; else if(cur.right != null) start = cur.right; } thisLevel.add(cur.val); if(cur.left != null) node.offer(cur.left); if(cur.right != null) node.offer(cur.right); } res.add(thisLevel); } return res; } }
Conclusion：
每次做树的题目总是很混乱，不论是递归还是用队列或者栈。要多多练习这方面的题目。
LeetCode -- Binary Tree Level Order Traversal
原文：http://www.cnblogs.com/little-YTMM/p/4855416.html