請實作一個函式按照之字形列印二叉樹，即第一行按照從左到右的順序列印，第二層按照從右至左的順序列印，第三行按照從左到右的順序列印，其他行以此類推
解題思路
這道題可以借助兩個堆疊來實作，用文字不好描述，也許直接看代碼會好一些
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
// 用來存放結點
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
if(pRoot == null) {
return list;
}
// 判斷奇偶層
int layer = 1;
// 存放奇數層結點
Stack<TreeNode> s1 = new Stack<>();
// 存放偶數層結點
Stack<TreeNode> s2 = new Stack<>();
// 先把根結點放入奇數層
s1.push(pRoot);
// 如果兩個堆疊都為空，那么就證明所有結點都已遍歷完畢
while(!s1.empty() || !s2.empty()) {
// 當前層是奇數層
if(layer % 2 != 0) {
// 存放奇數層的結點
ArrayList<Integer> temp = new ArrayList<>();
// 把奇數層的結點逐個彈出，用 temp 保存起來
// 同時把每個彈出結點的左右子結點壓入堆疊
// 要注意堆疊的特點是后進先出，因此出堆疊順序和入堆疊順序是相反的
while(!s1.empty()) {
TreeNode node = s1.pop();
if(node != null) {
temp.add(node.val);
s2.push(node.left);
s2.push(node.right);
}
}
if(!temp.isEmpty()) {
list.add(temp);
layer++;
}
} else {
// 原理同上
ArrayList<Integer> temp = new ArrayList<>();
while(!s2.empty()) {
TreeNode node = s2.pop();
if(node != null) {
temp.add(node.val);
s1.push(node.right);
s1.push(node.left);
}
}
if(!temp.isEmpty()) {
list.add(temp);
layer++;
}
}
}
return list;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/237922.html
標籤：其他
上一篇：對稱的二叉樹