本文主要是介绍算法—按之字形打印二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
分析
此题就是层序遍历变形而来。多了两个要求：
- 记录当前层数；
- 偶数层要倒序打印。
可以引用两个栈来解决，栈1存储奇数层的节点，栈2存储偶数层的节点。
listAll分层存放所有节点，是ArrayList<ArrayList< Integer >>类型。
-
如图，首先将根节点A压入stack1，并设置layer=1：
-
接下来循环处理stack1和stack2中的节点，前提是至少有一个栈非空，如果layer为奇数，则处理stack1的节点：
当stack1非空时，pop出stack1的节点：
-
然后将A添加到list1里面（list1存放奇数层节点的值，是ArrayList< Integer >类型），并将A的孩子从左到右push到stack2里面（这样出栈顺序就是倒序了）：
-
当stack1为空时，说明当前奇数层已经处理完毕，此时将layer++，并判断list1是否非空，若非空，则将list1加到listAll里面。
-
继续循环，若layer为偶数时，处理stack2中的节点，当stack2非空时，将stack2中的元素pop出：
-
并添加到list2中（list2存放偶数层节点），这样list2的存放顺序就是：C，B
-
同时将layer++
-
之后将C和B的孩子按从右到左的顺序push到stack1中（这是为了让stack1的出栈顺序是正序）：
之后再按照第一步的程序去处理stack1中的节点。直到stack1和stack2都为空为止。
代码
import java.util.ArrayList;
import java.util.Stack;public class Solution {public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();if(pRoot == null){return listAll;}Stack<TreeNode> s1 = new Stack<>(); //存奇数层节点Stack<TreeNode> s2 = new Stack<>(); //存偶数层节点s1.push(pRoot);int layer = 1; //记录层数while(!s1.isEmpty() || !s2.isEmpty()){if(layer%2 != 0){ //处理奇数层ArrayList<Integer> list1 = new ArrayList<>(); //存放当前奇数层的节点while(!s1.isEmpty()){TreeNode node = s1.pop();list1.add(node.val);if(node.left != null){s2.push(node.left);}if(node.right != null){s2.push(node.right);}}layer++;if(!list1.isEmpty()){listAll.add(list1);}}else{ //处理偶数层节点ArrayList<Integer> list2 = new ArrayList<>();while(!s2.isEmpty()){TreeNode node = s2.pop();list2.add(node.val);if(node.right != null){s1.push(node.right);}if(node.left != null){s1.push(node.left);}}layer++;if(!list2.isEmpty()){listAll.add(list2);}}}return listAll;}
}
这篇关于算法—按之字形打印二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
