題目
請實現(xiàn)一個函數(shù)按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印，其他行以此類推。
例如:
給定二叉樹:?[3,9,20,null,null,15,7],
??? 3
?? / \
? 9? 20
??? /? \
?? 15?? 7
返回其層次遍歷結(jié)果：
[
? [3],
? [20,9],
? [15,7]
]
提示：
節(jié)點總數(shù) <= 1000
解題思路
1.題目要求我們實現(xiàn)一個函數(shù)按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印，其他行以此類推。此題與【劍指 Offer 32 - II. 從上到下打印二叉樹 II】的解題思想幾乎一致，大家可以先去學習一下。
2.唯一的區(qū)別就是此題打印的順序不太一樣，我們經(jīng)過分析可以發(fā)現(xiàn)，奇數(shù)行的元素是正著打印的，偶數(shù)行的元素是倒著打印的。所以我們需要設(shè)置一個變量 sum 來記錄我們的行數(shù)，在往臨時動態(tài)數(shù)組 cur 中插入元素時，就需要判斷一下這個sum是奇數(shù)還是偶數(shù)，若為奇數(shù)，我們就直接add插入，若為偶數(shù)，我們就使用addFirst進行頭插，這樣插入的順序就是反著的。要注意的一點是，我們需要將臨時數(shù)組 cur 變?yōu)長inkedList ，因為只有LinkedList才有頭插法。
代碼實現(xiàn)
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
int sum = 1;
queue.add(root);
while(!queue.isEmpty()){
int k = queue.size();
LinkedList<Integer> cur = new LinkedList<>();
for(int i = 0; i < k; i++ ){
TreeNode t = queue.poll();
if(sum % 2 == 1){
cur.add(t.val);
}else{
cur.addFirst(t.val);
}
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
}
sum ++;
res.add(cur);
}
return res;
}
}測試結(jié)果
文章來源：http://www.zghlxwxcb.cn/news/detail-651815.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-651815.html
到了這里，關(guān)于Leetcode-每日一題【劍指 Offer 32 - III. 從上到下打印二叉樹 III】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
