請實現(xiàn)1個函數(shù)依照之字形打印2叉樹，即第1行依照從左到右的順序打印，第2層依照從右至左的順序打印，第3行依照從左到右的順序打印，其他行以此類推。
層次遍歷2叉樹很好理解
用隊列臨時寄存其中1層的結(jié)點，出隊列更新到下1層結(jié)點
按之字形順序打印2叉樹需要兩個棧。
在打印某1行結(jié)點時，把下1層的結(jié)點保存到相應(yīng)的棧里。如果當(dāng)前打印的是奇數(shù)層，則先保存左子結(jié)點再保存右子結(jié)點到第1個棧里；如果當(dāng)前打印的是偶數(shù)層，則先保存右結(jié)點在保存左子結(jié)點到第2個棧里。
import java.util.ArrayList;
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<Integer> row = new ArrayList<Integer>();
ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
if(pRoot == null)
return result;
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
boolean flag = true;
stack1.push(pRoot);
while(!stack1.isEmpty() || !stack2.isEmpty()){
row = new ArrayList<Integer>();
if(flag){
int size = stack1.size();
while((size--) >0){
TreeNode node = stack1.pop();
row.add(node.val);
if(node.left!=null)
stack2.push(node.left);
if(node.right!=null)
stack2.push(node.right);
}
flag = false;
}else{
int size = stack2.size();
while((size--) >0){
TreeNode node = stack2.pop();
row.add(node.val);
if(node.right!=null)
stack1.push(node.right);
if(node.left!=null)
stack1.push(node.left);
}
flag = true;
}
result.add(row);
}
return result;
}
}if else 程序?qū)懙暮艽?/p>
用隊列
層次遍歷輸出的每層元素都是左右的
對本題我們需要交叉的輸出
左右輸出
右左輸出
所有只需要對偶數(shù)的行在層次遍歷的基礎(chǔ)上進行逆序就行了
import java.util.ArrayList;
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<Integer> row = new ArrayList<Integer>();
ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
if(pRoot == null)
return result;
boolean flag = true;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(pRoot);
while(!queue.isEmpty()){
int size = queue.size();
row = new ArrayList<Integer>();
while((size--)>0){
TreeNode node = queue.poll();
row.add(node.val);
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
if(!flag){
reverse(row);
}
flag = !flag;
result.add(row);
}
return result;
}
public void reverse(ArrayList<Integer> list){
int i=0;
int j=list.size() -1;
while(i<j){
swap(list,i,j);
i++;
j--;
}
}
public void swap(ArrayList<Integer> list,int i,int j){
int a = list.get(i);
int b = list.get(j);
list.set(i,b);
list.set(j,a);
}
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
