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+ }
0 commit comments