Binary Tree Zigzag

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).

1. import java.util.Stack;
   
2. public class Solution {
   
3.     public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
   
4.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
   
5.         ArrayList<Integer> list = new ArrayList<Integer>();
   
6.         
   
7.         if(root == null) return result;
   
8.         
   
9.         LinkedList<TreeNode> parents = new LinkedList<TreeNode>();
   
10.         Stack<TreeNode> children = new Stack<TreeNode>();
    
11.         
    
12.         parents.add(root);
    
13.         while(!parents.isEmpty()){
    
14.             TreeNode parent = parents.remove();
    
15.             if(parent.left!=null) children.push(parent.left);
    
16.             if(parent.right!=null) children.push(parent.right);
    
17.             list.add(parent.val);
    
18.             if(parents.isEmpty()){
    
19.                 while(!children.empty()){
    
20.                     parents.add(children.pop());
    
21.                 }
    
22.                 children = new Stack<TreeNode>();
    
23.                 result.add(list);
    
24.                 list = new ArrayList<Integer>();
    
25.             }
    
26.         }
    
27.         return result;
    
28.     }
    
29. }

复制代码

有空的同学，帮忙看看这个哪儿写错了。。。
我自己在纸上过一遍应该是对的啊，搞不懂为什么test的5，4位置没变。
Wrong answer
Input:        {1,2,3,4,5}
Output:        [[1],[3,2],[5,4]]
Expected:        [[1],[3,2],[4,5]]

这题不应该用stack

题目里面每一层print的次序不一样，假如root是在第0层，那么偶数层是从左往右print，奇数层是从右往左print，你代码里用了stack，stack是FILO，因为你是先push入left child，再pushr入righ child，所以对于每个parent节点，都是先弹出的都是它的right child，再弹出它的left child，也就是说一直都是从右往左print，所以你结果那里4 5顺序就错了。

最好是一层一层的输出，然后用一个数组存每一层的节点，根据所在层的深度，决定print的方向。

RickyYe 发表于 2014-2-17 04:45
题目里面每一层print的次序不一样，假如root是在第0层，那么偶数层是从左往右print，奇数层是从右往左print ...

谢谢！
根据所在层的深度，是说要判断它是even／odd吗？

一地鸡毛 发表于 2014-2-16 15:19
谢谢！
根据所在层的深度，是说要判断它是even／odd吗？

是的，判断even odd就行了