摘要：題目要求對于一棵樹進行序遍歷。水平遍歷即遍歷結束當前行以后再遍歷下一行，并將每行的結果按行填入到數組中返回。利用水平遍歷的話，我們只需要知道當前元素在樹中的高度就可以知道應當插入到那個數組中。
題目要求
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,null,null,15,7],
3
/
9 20
/
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
對于一棵樹進行level序遍歷。水平遍歷即遍歷結束當前行以后再遍歷下一行，并將每行的結果按行填入到數組中返回。
遞歸
這道題還是很基礎的啦。利用水平遍歷的話，我們只需要知道當前元素在樹中的高度就可以知道應當插入到那個數組中。
public List> levelOrder(TreeNode root) {
List> result = new ArrayList>();
levelOrder(root, 0, result);
return result;
}
public void levelOrder(TreeNode treeNode, int height, List> result){
if(treeNode == null) return;
if(height>result.size()-1){
result.add(new ArrayList());
}
result.get(height).add(treeNode.val);
levelOrder(treeNode.left, height+1, result);
levelOrder(treeNode.right, height+1, result);
}
使用隊列
其實在數據結構的教材中為了說明棧和隊列的使用，分別舉的就是中序遍歷和水平遍歷的例子。在這里我們同樣可以使用隊列的先進先出的機制將同一行的元素讀入后，再逐個讀出，并在同時插入下一行中的元素。
public List> levelOrder2(TreeNode root){
List> result = new ArrayList>();
if(root==null)return result;
Queue queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()){
int levNum = queue.size();
List temp = new ArrayList();
for(int i = 0 ; i
想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71144.html
