-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathBTPosOrder.h
More file actions
117 lines (104 loc) · 3.27 KB
/
BTPosOrder.h
File metadata and controls
117 lines (104 loc) · 3.27 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/*
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
/*
1.1 Create an empty stack
2.1 Do following while root is not NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
*/
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> mystack;
if(root == NULL) return result;
if(root->right!=NULL)
mystack.push(root->right);
mystack.push(root);
root = root->left;
while(!mystack.empty()){
/**************************************
Do following while root is not NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
**************************************/
while(root)
{
if(root->right!=NULL)
mystack.push(root->right);
mystack.push(root);
cout << "adding value:"<<root->val<<endl;
root = root->left;
}
//pop the item from the stack
root = mystack.top();
mystack.pop();
/******************************
If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
********************************************/
if(root->right && !mystack.empty() && root->right == mystack.top())
{
mystack.pop();
mystack.push(root);
root = root->right;
}
else
{
result.push_back(root->val);
root = NULL;
}
}
return result;
}
};
/**** another decent solution****/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> output;
if(root == NULL)
return output;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty())
{
TreeNode *t = stk.top();
stk.pop();
output.push_back(t->val);
if(t->left)
stk.push(t->left);
if(t->right)
stk.push(t->right);
}
reverse(output.begin(), output.end());
return output;
}
};