1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Nov 20, 2014
4+ Problem: Binary Tree Postorder Traversal
5+ Difficulty: Easy
6+ Source: http://oj.leetcode.com/problems/binary-tree-postorder-traversal/
7+ Notes:
8+ Given a binary tree, return the postorder traversal of its nodes' values.
9+
10+ For example:
11+ Given binary tree {1,#,2,3},
12+ 1
13+ \
14+ 2
15+ /
16+ 3
17+ return [3,2,1].
18+
19+ Note: Recursive solution is trivial, could you do it iteratively?
20+
21+ Solution: 1. Iterative way (stack). Time: O(n), Space: O(n).
22+ 2. Recursive solution. Time: O(n), Space: O(n).
23+ 3. Threaded tree (Morris). Time: O(n), Space: O(n/1).
24+ Space: O(1) if in-place reverse.
25+ You may refer to my blog for more detailed explanations:
26+ http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html
27+ */
28+
29+
30+ /**
31+ * Definition for binary tree
32+ * public class TreeNode {
33+ * int val;
34+ * TreeNode left;
35+ * TreeNode right;
36+ * TreeNode(int x) { val = x; }
37+ * }
38+ */
39+ public class Solution {
40+ public List <Integer >postorderTraversal_1 (TreeNode root ) {
41+ List <Integer >res =new ArrayList <Integer >();
42+ if (root ==null )return res ;
43+ Stack <TreeNode >stk =new Stack <TreeNode >();
44+ TreeNode cur =root ;
45+ TreeNode pre =null ;
46+ while (stk .isEmpty () ==false ||cur !=null ) {
47+ if (cur !=null ) {
48+ stk .push (cur );
49+ cur =cur .left ;
50+ }else {
51+ TreeNode peak =stk .peek ();
52+ if (peak .right !=null &&pre !=peak .right ) {
53+ cur =peak .right ;
54+ }else {
55+ res .add (peak .val );
56+ stk .pop ();
57+ pre =peak ;
58+ }
59+ }
60+ }
61+ return res ;
62+ }
63+ public List <Integer >postorderTraversal_2 (TreeNode root ) {
64+ List <Integer >res =new ArrayList <Integer >();
65+ if (root ==null )return res ;
66+ List <Integer >left =postorderTraversal (root .left );
67+ List <Integer >right =postorderTraversal (root .right );
68+ res .addAll (left );
69+ res .addAll (right );
70+ res .add (root .val );
71+ return res ;
72+ }
73+ public List <Integer >postorderTraversal_3 (TreeNode root ) {
74+ List <Integer >res =new ArrayList <Integer >();
75+ if (root ==null )return res ;
76+ Stack <Integer >stk =new Stack <Integer >();
77+ TreeNode dummy =new TreeNode (-1 );
78+ dummy .left =root ;
79+ TreeNode cur =dummy ;
80+ while (cur !=null ) {
81+ if (cur .left ==null ) {
82+ cur =cur .right ;
83+ }else {
84+ TreeNode node =cur .left ;
85+ while (node .right !=null &&node .right !=cur )
86+ node =node .right ;
87+ if (node .right ==null ) {
88+ node .right =cur ;
89+ cur =cur .left ;
90+ }else {
91+ TreeNode temp =cur .left ;
92+ while (temp !=cur ) {
93+ stk .push (temp .val );
94+ temp =temp .right ;
95+ }
96+ while (stk .isEmpty () ==false )res .add (stk .pop ());
97+ node .right =null ;
98+ cur =cur .right ;
99+ }
100+ }
101+ }
102+ return res ;
103+ }
104+ }
