现在很多网站都是wordpress/小说引流推广

题目描述:

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，
其他行以此类推。

题目描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树之字形层序遍历的结果是

[

[3],

[20,9],

[15,7]

]

示例1

输入

{1,#,2}

输出

[[1],[2]]

解题思路： 

 按之字形顺序打印二叉树需要两个栈。我们在打印某一行结点时，把下一层的子结点保存到相应的栈里。如果当前打印的是奇数层，则先保存左子结点再保存右子结点到一个栈里；如果当前打印的是偶数层，则先保存右子结点再保存左子结点到第二个栈里。

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;* }*/public class Solution {/*** * @param root TreeNode类 * @return int整型ArrayList<ArrayList<>>*/public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {ArrayList<ArrayList<Integer>>  result = new ArrayList<ArrayList<Integer>>();if(root == null){return result;}//奇数层的栈Stack<TreeNode> stack1 = new Stack<>();//偶数层的栈Stack<TreeNode> stack2 = new Stack<>();int level = 1;stack1.push(root);while(!stack1.isEmpty() || !stack2.isEmpty()){//下面的if else if 保证了奇数、偶数每次只遍历一次 并且创建一个新的listArrayList<Integer> list = new ArrayList<>();if(level%2 == 1){while(!stack1.isEmpty()){TreeNode temp1 = stack1.pop();list.add(temp1.val);//如果左节点不为null 加入stack2if(temp1.left != null){stack2.add(temp1.left);}//如果右节点不为null 加入stack2if(temp1.right != null){stack2.add(temp1.right);}}//每一层遍历完成之后 层数+1level++;result.add(list);}else if(level%2 == 0){while(!stack2.isEmpty()){TreeNode temp2 = stack2.pop();list.add(temp2.val);//如果右节点不为null 加入stack1if(temp2.right != null){stack1.add(temp2.right);}//如果左节点不为null 加入stack1if(temp2.left != null){stack1.add(temp2.left);}}//每一层遍历完成之后 层数+1level++;result.add(list);}}return result;}}