不分層：
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode treeNode = queue.poll();
result.add(treeNode.val);
if (treeNode.left != null) queue.offer(treeNode.left);
if (treeNode.right != null) queue.offer(treeNode.right);
}
return result;
}
從上到下按層打印二叉樹溯香，同一層結(jié)點(diǎn)從左至右輸出鲫构。每一層輸出一行。（分層）
思路一：利用隊列玫坛，層次遍歷的方式结笨，存入list
// 也是分行打印，比上面簡潔
public void printEveryLayer(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int layerSize = queue.size();
for (int i = 0; i < layerSize; i++) {
TreeNode node = queue.poll();
System.out.println(node.val+" ");
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
System.out.println();
}
}
/**
* 統(tǒng)計隊列中每一層的節(jié)點(diǎn)數(shù)昂秃，循環(huán)添加
* @param pRoot
* @return
*/
ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(pRoot);
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
if (pRoot == null) return lists;
ArrayList<Integer> layerList = new ArrayList<>();
while (!queue.isEmpty()){
int layerSize = queue.size();
//每次都將每一行統(tǒng)計完再出循環(huán)禀梳，進(jìn)入下一行
for (int i=0;i<layerSize;++i){
TreeNode temp = queue.poll();
layerList.add(temp.val);
if (temp.left != null) queue.offer(temp.left);
if (temp.right != null) queue.offer(temp.right);
}
lists.add(new ArrayList<Integer>(layerList));
layerList.clear();
}
return lists;
}
思路二：
遞歸構(gòu)造一個參數(shù)為根節(jié)點(diǎn)杜窄，當(dāng)前深度肠骆，和list的節(jié)點(diǎn)。遞歸左右節(jié)點(diǎn)塞耕，每次深度加1
/**
* 遞歸解法
* @param pRoot
* @return
*/
ArrayList<ArrayList<Integer>> Print2(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
depth(pRoot,1,lists);
return lists;
}
private void depth(TreeNode treeNode, int depth, ArrayList<ArrayList<Integer>> lists) {
if (treeNode == null) return;
//深度改變時蚀腿，才往集合中加入新的list
if (depth > lists.size()){
lists.add(new ArrayList<Integer>());
}
//直接將該節(jié)點(diǎn)值接如最后的list中
lists.get(depth-1).add(treeNode.val);
depth(treeNode.left,depth+1,lists);
depth(treeNode.right,depth+1,lists);
}
思路三：設(shè)置兩個變量，記錄層次和每層的數(shù)量扫外。
/**
* 思路莉钙，增加兩個變量分別表示當(dāng)前行的節(jié)點(diǎn)數(shù)目和下一行的節(jié)點(diǎn)數(shù)目
* 每打印一次當(dāng)前行減一，每添加一次子節(jié)點(diǎn)下一行加1
* 當(dāng)前行為0時賦值下一行筛谚，下一行清0
* @param pRoot
* @return
*/
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
int toBePrinted = 1;
int nextLevel = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(pRoot);
if (pRoot == null) return list;
//放在循壞里會變成每次只有一個
ArrayList<Integer> perList = new ArrayList<>();
while (!queue.isEmpty()){
TreeNode temp = queue.poll();
perList.add(temp.val);
toBePrinted--;
if (temp.left != null){
queue.offer(temp.left);
nextLevel++;
}
if (temp.right != null){
queue.offer(temp.right);
nextLevel++;
}
if (toBePrinted == 0){
list.add(new ArrayList<Integer>(perList));
//直接把內(nèi)存地址清空
perList.clear();
/**
* 或者采用如下注釋
*
*/
// list.add(perList);
// perList = new ArrayList<Integer>();
toBePrinted = nextLevel;
nextLevel = 0;
}
}
return list;
}
請實(shí)現(xiàn)一個函數(shù)按照之字形打印二叉樹磁玉，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印驾讲，第三行按照從左到右的順序打印蚊伞，其他行以此類推。
用兩個棧去分奇偶行記錄下一行吮铭，主要體現(xiàn)在出棧存儲下一行的區(qū)別上
當(dāng)前奇數(shù)行时迫，下一行偶數(shù)行要從右向左打印，先記錄左節(jié)點(diǎn)谓晌，右節(jié)點(diǎn)先出掠拳。
當(dāng)前偶數(shù)行，下一行奇數(shù)行從左向右打印纸肉，先記錄右節(jié)點(diǎn)溺欧，左節(jié)點(diǎn)先出喊熟。
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/**
* 兩個棧記錄不同方向的輸出，一個記錄奇數(shù)行從左到右胧奔，一個記錄偶數(shù)行從右到左逊移，循環(huán)打印
* 打印后一行后，改變左右節(jié)點(diǎn)的放入順序龙填，先進(jìn)先出
* @param pRoot
* @return
*/
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
if (pRoot == null) return lists;
LinkedList<TreeNode> stackOdd = new LinkedList<>();
LinkedList<TreeNode> stackEven = new LinkedList<>();
stackOdd.push(pRoot);
//有一個不為空胳泉，則循環(huán)繼續(xù)
while (!stackOdd.isEmpty() || !stackEven.isEmpty()){
ArrayList<Integer> perList = new ArrayList<>();
if (!stackOdd.isEmpty()){
while (!stackOdd.isEmpty()){
TreeNode temp = stackOdd.pop();
perList.add(temp.val);
if (temp.left != null) stackEven.push(temp.left);
if (temp.right != null) stackEven.push(temp.right);
}
}else {
while (!stackEven.isEmpty()){
TreeNode temp = stackEven.pop();
perList.add(temp.val);
if (temp.right != null) stackOdd.push(temp.right);
if (temp.left != null) stackOdd.push(temp.left);
}
}
lists.add(perList);
}
return lists;
}
