摘要：題目要求對于一棵樹進(jìn)行序遍歷。水平遍歷即遍歷結(jié)束當(dāng)前行以后再遍歷下一行，并將每行的結(jié)果按行填入到數(shù)組中返回。利用水平遍歷的話，我們只需要知道當(dāng)前元素在樹中的高度就可以知道應(yīng)當(dāng)插入到那個(gè)數(shù)組中。
題目要求
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]
]
對于一棵樹進(jìn)行l(wèi)evel序遍歷。水平遍歷即遍歷結(jié)束當(dāng)前行以后再遍歷下一行，并將每行的結(jié)果按行填入到數(shù)組中返回。
遞歸
這道題還是很基礎(chǔ)的啦。利用水平遍歷的話，我們只需要知道當(dāng)前元素在樹中的高度就可以知道應(yīng)當(dāng)插入到那個(gè)數(shù)組中。
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);
}
使用隊(duì)列
其實(shí)在數(shù)據(jù)結(jié)構(gòu)的教材中為了說明棧和隊(duì)列的使用，分別舉的就是中序遍歷和水平遍歷的例子。在這里我們同樣可以使用隊(duì)列的先進(jìn)先出的機(jī)制將同一行的元素讀入后，再逐個(gè)讀出，并在同時(shí)插入下一行中的元素。
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
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/71144.html
