题解 JAVA Deque | #按之字形顺序打印二叉树# [P1]

按之字形顺序打印二叉树

http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

正常level-order traversal(因为比较好理解). 在visit的时候,用Deque去存值(因为Deque既是Queue也是Stack)。如果正向就当Queue(i.e. offer), 反向就当stack(i.e. push)。最后用Collection的copy constructor把Deque转化成ArrayList。

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
      ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
      if (pRoot == null) return ret;
      
      Queue<TreeNode> q = new LinkedList<>();
      boolean odd = true;
      q.offer(pRoot);
      while (!q.isEmpty()) {
        int lSize = q.size();
        Deque<Integer> levelDeq = new ArrayDeque<>();
        while (lSize > 0) { 
          TreeNode n = q.poll();
          if (odd) levelDeq.offer(n.val);
          else levelDeq.push(n.val);  // offerFirst
        
          if (n.left != null) q.offer(n.left);
          if (n.right != null) q.offer(n.right);
          lSize--;
        }
        odd = !odd;
        ret.add(new ArrayList<>(levelDeq));
      }
      return ret;
    }
}
全部评论

相关推荐

不放弃的小鱼干很洒脱:好可爱的离职理由
点赞 评论 收藏
分享
02-08 20:56
已编辑
南京工业大学 Java
在等offer的比尔很洒脱:我也是在实习,项目先不说,感觉有点点小熟悉,但是我有点疑问,这第一个实习,公司真的让实习生去部署搭建和引入mq之类的吗,是不是有点过于信任了,我实习过的两个公司都是人家正式早搭好了,根本摸不到部署搭建的
点赞 评论 收藏
分享
评论
3
1
分享

创作者周榜

更多
牛客网
牛客企业服务