首页 » Java » 103. Binary Tree Zigzag Level Order Traversal

103. Binary Tree Zigzag Level Order Traversal

2016-11-05 16:40:10阅读(381)

/**
 * Definition for a Binary Tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   public List<List<Integer>> ZigzagLevelOrder(TreeNode root) {
        Queue<TreeNode>queue1 = new LinkedList<>();//这个是用了放偶数层的节点的;
        Queue<TreeNode>queue2 = new LinkedList<>();//这个是用来放奇数成的节点的;
        Stack<TreeNode>stack  = new Stack<>();
        List<Integer> list = new ArrayList<>();
        List<List<Integer>>ll = new ArrayList<>();
        if (root==null)return ll;
        queue1.add(root);
        int i=0;
       while (!queue1.isEmpty()||!queue2.isEmpty()){
           list =new ArrayList<>();
           //因为我是往队列里先加入右节点再加入左节点,所以偶数层的时候需要用stack颠倒输出的数。
           if (i%2==0){
               while (!queue1.isEmpty()) {
                   TreeNode node = queue1.poll();
                   stack.push(node);
                   if (node.right!=null)queue2.add(node.right);
                   if (node.left!=null)queue2.add(node.left);
               }
               while (!stack.isEmpty()){
                   list.add(stack.pop().val);
               }
               ll.add(list);
               i++;
               continue;
           }else {
               while (!queue2.isEmpty()){
                   TreeNode node = queue2.poll();
                   list.add(node.val);
                   if (node.right!=null)queue1.add(node.right);
                   if (node.left!=null)queue1.add(node.left);
               }
               ll.add(list);
               i++;
               continue;
           }
       }
       return ll;
    }
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹