一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 655|回复: 4
收起左侧

[Leetcode] Binary Tree Zigzag

[复制链接] |试试Instant~ |关注本帖
一地鸡毛 发表于 2014-2-16 07:44:44 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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]]
kelvinzhong 发表于 2014-2-17 01:11:12 | 显示全部楼层
这题不应该用stack
回复 支持 反对

使用道具 举报

RickyYe 发表于 2014-2-17 04:45:36 | 显示全部楼层
题目里面每一层print的次序不一样,假如root是在第0层,那么偶数层是从左往右print,奇数层是从右往左print,你代码里用了stack,stack是FILO,因为你是先push入left child,再pushr入righ child,所以对于每个parent节点,都是先弹出的都是它的right child,再弹出它的left child,也就是说一直都是从右往左print,所以你结果那里4 5顺序就错了。

最好是一层一层的输出,然后用一个数组存每一层的节点,根据所在层的深度,决定print的方向。
回复 支持 反对

使用道具 举报

 楼主| 一地鸡毛 发表于 2014-2-17 05:19:13 | 显示全部楼层

谢谢!
根据所在层的深度,是说要判断它是even/odd吗?
回复 支持 反对

使用道具 举报

RickyYe 发表于 2014-2-17 05:48:08 | 显示全部楼层
一地鸡毛 发表于 2014-2-16 15:19
谢谢!
根据所在层的深度,是说要判断它是even/odd吗?

是的,判断even odd就行了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 21:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表