按之字形顺序打印二叉树
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。 ***
思路
用dfs递归遍历所有点，存在二维数组中，然后用Collections.reverse()把偶数行翻转即可。 偷懒了偷懒了。 后来我看到大佬是用两个栈来做的，一个存奇数行，一个存偶数行。当输出奇数行时，将其从栈中取出，把其儿子结点存进偶数的栈。反之亦然。
Java实现
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 static ArrayList<ArrayList<Integer> > ans;
public static void dfs(TreeNode root, int d) {
while(ans.size()-1<d) {
ans.add(new ArrayList<Integer>());
}
ans.get(d).add(root.val);
if(root.left!=null){
dfs(root.left, d+1);
}
if(root.right!=null){
dfs(root.right, d+1);
}
}
public static ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ans = new ArrayList<ArrayList<Integer> >();
if(pRoot==null){
return ans;
}
dfs(pRoot, 0);
for(int i=1; i<=ans.size();i++) {
if((i&1)==0){
Collections.reverse(ans.get(i-1));
}
}
return ans;
}
}
