一共三道要求不同的打印方式的從上到下打印二叉樹(shù)
第一道：
/從上到下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同一層的節(jié)點(diǎn)按照從左到右的順序打印。/
例如:
給定二叉樹(shù): [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
提示：
節(jié)點(diǎn)總數(shù) <= 1000
思路：
這道題本質(zhì)就是二叉樹(shù)的層序遍歷慷妙，直接擼
class Solution {
public int[] levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> list = new ArrayList<>();
if(root != null)
queue.offer(root);
while(queue.size() != 0){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null)
queue.offer(node.left);
if(node.right != null)
queue.offer(node.right);
}
// 將結(jié)果轉(zhuǎn)為 int[]
int[] result = new int[list.size()];
int index = 0;
for(Integer i : list)
result[index ++] = i;
return result;
}
}
第二道：
/從上到下按層打印二叉樹(shù)，同一層的節(jié)點(diǎn)按從左到右的順序打印湿弦，每一層打印到一行衷恭。/
例如:
給定二叉樹(shù): [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其層次遍歷結(jié)果：
[
[3],
[9,20],
[15,7]
]
提示：
節(jié)點(diǎn)總數(shù) <= 1000
思路：
層序打印的同時(shí)，維護(hù)兩個(gè)變量 cur（當(dāng)前層的數(shù)量）堤撵、next（下一層的數(shù)量）仁讨。
每次隊(duì)列 poll 出一個(gè)節(jié)點(diǎn)時(shí)，cur 減一实昨，如果該結(jié)點(diǎn)存在孩子節(jié)點(diǎn)洞豁，則 next 加上孩子節(jié)點(diǎn)的數(shù)量（下一層的數(shù)量）。當(dāng) cur == 0 時(shí)荒给，即當(dāng)前層數(shù)的節(jié)點(diǎn)打印完丈挟，開(kāi)始下一層的打印 cur = next。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
ArrayList<List<Integer>> result = new ArrayList();
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> line = new ArrayList<>();
int cur = 0, next = 0; // 當(dāng)前層的數(shù)量志电，下一層的數(shù)量
if(root != null)
queue.offer(root);
cur = 1;
while(queue.size() != 0){
TreeNode node = queue.poll();
line.add(node.val);
if(node.left != null){
queue.offer(node.left);
next ++;
}
if(node.right != null){
queue.offer(node.right);
next ++;
}
// 當(dāng)前層數(shù)打印完曙咽，開(kāi)始打印下一層。
if(--cur == 0){
result.add(line);
line = new ArrayList<>();
cur = next;
next = 0;
}
}
if(line.size() != 0)
result.add(line);
return result;
}
}
第三道
/請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形順序打印二叉樹(shù)挑辆，即第一行按照從左到右的順序打印例朱，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印鱼蝉，其他行以此類(lèi)推洒嗤。/
例如:
給定二叉樹(shù): [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其層次遍歷結(jié)果：
[
[3],
[20,9],
[15,7]
]
解答：
利用雙棧 left （出棧的順序等于該層次從左到右打印的順序），right（出棧的順序等于該層次從右到左打印的順序）魁亦， 同時(shí)利用一個(gè) boolean 類(lèi)型 turn 來(lái)控制遍歷的方式渔隶，turn = true時(shí)：從左到右打印，turn = false 時(shí)洁奈，從右到左打印间唉。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> line = new ArrayList<>();
Stack<TreeNode> left = new Stack<>();
Stack<TreeNode> right = new Stack<>();
boolean turn = true; //true:左到右遍歷， false 反之
if(root != null)
left.push(root);
while(left.size()!=0 || right.size()!=0){
TreeNode node = turn? left.pop() : right.pop();
line.add(node.val);
// 從左開(kāi)始遍歷與從右開(kāi)始遍歷睬魂，入對(duì)應(yīng)的棧的順序不同
if(turn){
if(node.left != null)
right.push(node.left);
if(node.right != null)
right.push(node.right);
}else{
if(node.right != null)
left.push(node.right);
if(node.left != null)
left.push(node.left);
}
// 控制下一層的轉(zhuǎn)向
if(turn && left.isEmpty()){
turn = false;
result.add(line);
line = new ArrayList<>();
}else if(!turn && right.isEmpty()){
turn = true;
result.add(line);
line = new ArrayList<>();
}
}
if(line.size() != 0)
result.add(line);
return result;
}
}
利用隊(duì)列解決终吼，
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
if(res.size() % 2 == 1) Collections.reverse(tmp);
res.add(tmp);
}
return res;
}
}
