Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree
Given binary tree
{3,9,20,#,#,15,7}
,3 / \ 9 20 / \ 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]Solution:O(n)
public class Solution { public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); if(root==null) return ret; boolean order = true; ArrayList<TreeNode> toVisit = new ArrayList<TreeNode>(); toVisit.add(root); while(!toVisit.isEmpty()){ ArrayList<TreeNode> next = new ArrayList<TreeNode>(); ArrayList<Integer> tmp = new ArrayList<Integer>(); for(TreeNode node:toVisit){ tmp.add(node.val); } ret.add(tmp); for(int i=toVisit.size()-1;i>=0;i--){ TreeNode node = toVisit.get(i); if(order){ if(node.right!=null) next.add(node.right); if(node.left!=null) next.add(node.left); }else{ if(node.left!=null) next.add(node.left); if(node.right!=null) next.add(node.right); } } order = !order; toVisit = new ArrayList<TreeNode>(next); } return ret; } }
沒有留言:
張貼留言