按之字形顺序打印二叉树

1.题目

2.解法（双栈法）

import java.util.Queue; import java.util.ArrayList; import java.util.Stack; public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> arr = new ArrayList<>(); // 1.如果根节点为空 if (pRoot == null) return arr; // 2.声明两个栈, s1存储从左向右的结点，s2存储从右向左的结点 Stack<TreeNode> s1 = new Stack<>(); Stack<TreeNode> s2 = new Stack<>(); s1.push(pRoot); TreeNode tmp = null; ArrayList<Integer> tmpArr = null; while (s1.size() > 0 || s2.size() > 0) { // 这段代码可以重复使用 tmpArr = new ArrayList<>(); if(s1.size() > 0) { while (!s1.isEmpty()) { // 删除结点的同时，存储下一层的结点 tmp = s1.pop(); tmpArr.add(tmp.val); if (tmp.left != null) { s2.push(tmp.left); } if (tmp.right != null) { s2.push(tmp.right); } } arr.add(tmpArr); continue; } if(s2.size() > 0){ while (!s2.isEmpty()) { tmp = s2.pop(); tmpArr.add(tmp.val); if (tmp.right != null) { s1.push(tmp.right); } if (tmp.left != null) { s1.push(tmp.left); } } arr.add(tmpArr); } } return arr; } }

时间复杂度为O(n),空间复杂度为O(n)