The recursive solution is trivial and I omit it here.
Iterative Solution using Stack (O(n) time and O(n) space):
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
// write your code here
vector<int> nodes;
TreeNode* node = root;
TreeNode* lastNode = NULL;
stack<TreeNode*> toVisit;
while (node || !toVisit.empty()) {
if (node) {
toVisit.push(node);
node = node -> left;
}
else {
TreeNode* topNode = toVisit.top();
if (topNode -> right && topNode -> right != lastNode)
node = topNode -> right;
else {
nodes.push_back(topNode -> val);
lastNode = topNode;
toVisit.pop();
}
}
}
return nodes;
}
};
Another sophisticated solution using Morris Traversal (O(n) time and O(1) space):
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
// write your code here
vector<int> nodes;
TreeNode* dump = new TreeNode();
dump -> left = root;
TreeNode* node = dump;
while (node) {
if (node -> left) {
TreeNode* predecessor = node -> left;
while (predecessor -> right && predecessor -> right != node)
predecessor = predecessor -> right;
if (!(predecessor -> right)) {
predecessor -> right = node;
node = node -> left;
}
else {
reverseAddNodes(node -> left, predecessor, nodes);
predecessor -> right = NULL;
node = node -> right;
}
}
else node = node -> right;
}
return nodes;
}
private:
void reverseNodes(TreeNode* start, TreeNode* end) {
TreeNode* x = start;
TreeNode* y = start -> right;
TreeNode* z;
while (x != end) {
z = y -> right;
y -> right = x;
x = y;
y = z;
}
}
void reverseAddNodes(TreeNode* start, TreeNode* end, vector<int>& nodes) {
reverseNodes(start, end);
TreeNode* node = end;
while (true) {
nodes.push_back(node -> val);
if (node == start) break;
node = node -> right;
}
reverseNodes(end, start);
}
};