一． 问题描述
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
二． 解题思路
本题思路：采用递归+广度优先遍历的方法进行求解
步骤一：构建遍历函数(全局变量list存储数据，局部变量data存储当前的节点数，标记量mark判断是从左往右开始遍历，还是从右往左开始遍历)
步骤二： 在递归函数中进行层序遍历，当遇到奇数层时，对data数据从左往右遍历得到数据，存储在list中,并将其各个子树从左往右存储到新data中，将标记mark=-1；
步骤三：在递归函数中进行层序遍历，当遇到偶数层时，对data数据从右往左遍历得到数据,存储在list中,并将其各个子树从左往右存储到新data中，将标记mark=-1；
步骤四：当data不为空时返回步骤二，当为空时返回list列表。
三． 执行结果
执行用时 :1 ms, 在所有 java 提交中击败了100.00%的用户
内存消耗 :36 MB, 在所有 java 提交中击败了40.11%的用户
四． Java代码
class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> list=new ArrayList<List<Integer>>(); if(root==null) { return list; } List<TreeNode> data=new ArrayList<TreeNode>(); data.add(root); treeNo(list,data,1); return list; } public void treeNo(List<List<Integer>> list,List<TreeNode> data,int mark) { if(data.size()==0) { return; } List<TreeNode> tempdata=new ArrayList<TreeNode>(); List<Integer> temp=new ArrayList<Integer>(); if(mark==1) { for(int i=0;i<data.size();i++) { temp.add(data.get(i).val); if(data.get(i).left!=null) { tempdata.add(data.get(i).left); } if(data.get(i).right!=null) { tempdata.add(data.get(i).right); } } mark=-1; }else { for(int i=data.size()-1,j=0;i>=0||j<data.size();i--,j++) { temp.add(data.get(i).val); if(data.get(j).left!=null) { tempdata.add(data.get(j).left); } if(data.get(j).right!=null) { tempdata.add(data.get(j).right); } } mark=1; } list.add(temp); treeNo(list,tempdata,mark); } }
原文：https://www.cnblogs.com/xiaobaidashu/p/11809531.html