找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1303|回复: 1
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Binary Tree PostOrder Traversal】-【刷题第一弹2014】

[复制链接]

18

主题

11

精华

478

积分

高级会员

Rank: 3Rank: 3

积分
478
发表于 10-13-2014 02:07 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 wyu277 于 10-13-2014 02:12 PM 编辑

Binary Tree PostOrder Traversal
传送门

题目:

Given a binary tree, return the postorder traversal of its nodes' values.


汇总帖传送门

相关题目:
Binary Tree PreOrder Traversal
Binary Tree InOrder Traversal
Binary Tree Level Order Traversal I,II


本帖被以下淘专辑推荐:

18

主题

11

精华

478

积分

高级会员

Rank: 3Rank: 3

积分
478
 楼主| 发表于 10-13-2014 02:32 PM | 显示全部楼层
本帖最后由 wyu277 于 10-13-2014 02:34 PM 编辑

题没什么难的,关键大家只要理解什么是
1. PostOrder traversal    (left right root)
2. PreOrder traversal      (root left right)
3. InOrder traversal        (left root right)

这些 都是针对什么时候遍历 root node 而得名的。

两种方法:
recursive 或者 iterative

recursive 没什么好纠结的:

  1. public List<Integer> postorderTraversal(TreeNode root) {
  2.     List<Integer> result = new ArrayList<>();
  3.     if (root == null)   {return result;}
  4.    
  5.     postOrderRecur(root,result);
  6.    
  7.     return result;
  8. }

  9. static void postOrderRecur(TreeNode root, List<Integer> result)
  10. {
  11.     if (root == null)   {return;}
  12.    
  13.     postOrderRecur(root.left,result);
  14.     postOrderRecur(root.right,result);
  15.     result.add(root.val);
  16. }
复制代码


Iterative:
基本上所有的recursive method 转化为 iterative 的都需要一个堆栈进行memorize的操作PostOrder 的关键就在于,这个peeknode 和 lastpeek 消除 死循环。
标记哪些点 已经 visited了。 你当然也可以用一个array 来记录。

  1. public List<Integer> postorderTraversal(TreeNode root) {
  2.     List<Integer> result = new ArrayList<>();
  3.     if (root == null)   {return result;}
  4.    
  5.     TreeNode curr = root;
  6.     TreeNode lastpeek = null;
  7.     Stack<TreeNode> parent = new Stack<>();
  8.    
  9.     while (curr!=null||!parent.isEmpty())
  10.     {   
  11.         if (curr!=null)
  12.         {
  13.             parent.push(curr);
  14.             curr = curr.left;
  15.         }
  16.         else
  17.         {
  18.             TreeNode peeknode = parent.peek();
  19.             if (peeknode.right!=null&&peeknode.right!=lastpeek)
  20.             {
  21.                 curr = peeknode.right;
  22.             }
  23.             else
  24.             {
  25.                 lastpeek = parent.pop();
  26.                 result.add(lastpeek.val);
  27.             }
  28.         }
  29.     }
  30.    
  31.     return result;
  32. }
复制代码

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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