给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回锯齿形层次遍历如下:[ [3], [20,9], [15,7]]详见:https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/Java实现:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List
> zigzagLevelOrder(TreeNode root) { List
> res=new ArrayList
>(); if(root==null){ return res; } LinkedList que=new LinkedList (); que.offer(root); int curNode=1; boolean leftToRight=true; ArrayList list=new ArrayList (); while(!que.isEmpty()){ root=que.poll(); --curNode; if(root.left!=null){ que.offer(root.left); } if(root.right!=null){ que.offer(root.right); } list.add(root.val); if(curNode==0){ curNode=que.size(); if(leftToRight){ res.add(list); }else{ res.add(reverseList(list)); } leftToRight=!leftToRight; list=new ArrayList (); } } return res; } private ArrayList reverseList(ArrayList list){ ArrayList res=new ArrayList (); for(int i=list.size()-1;i>=0;--i){ res.add(list.get(i)); } return res; }}