# 145. Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [3,2,1]
# Solution
Approach 1: recursion.
Approach 2: iteration -- essentially preorder traversal, reversed (but make sure to visit the right subtree first before reversal). Can do Morris traversal too.
Approach 3: iteration(python only) -- use an additional flag for each item in the stack to indicate whether the node has been visited. Each node gets put onto the stack twice, unvisited(expand child nodes when popped), and visited(its own value to be appended in the end).
# Code (Python)
Approach 1:
class Solution:
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
# recursive
if not root:
return []
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
Approach 2:
def postorderTraversal(self, root):
# iterative: essentially preorder traversal, reversed
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
stack.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
Approach 3:
def postorderTraversal(self, root):
# iterative: use additional marker to see if the top node is visited yet
if not root:
return []
result = []
stack = [(root, False)] # haven't visited the root node initially
while stack:
node, visited = stack.pop()
if visited:
result.append(node.val)
else:
stack.append((node, True)) # so that node's val gets added eventually
if node.right:
stack.append((node.right, False))
if node.left:
stack.append((node.left, False))
return result
# Code (C++)
Approach 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// Recursion.
class Solution {
private:
vector<int> res;
void doPostorderTraversal(TreeNode* root) {
if (root == NULL)
return;
if (root->left)
doPostorderTraversal(root->left);
if (root->right)
doPostorderTraversal(root->right);
res.push_back(root->val);
}
public:
vector<int> postorderTraversal(TreeNode* root) {
doPostorderTraversal(root);
return res;
}
};
Approach 2:
// Iteration (reverse left-right-reversed-preorder traversal)
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
if (root)
st.push(root);
while (!st.empty())
{
TreeNode *node = st.top();
st.pop();
res.push_back(node->val);
if (node->left)
st.push(node->left);
if (node->right)
st.push(node->right);
}
// while (root) {
// res.push_back(root->val);
// if (root->left)
// st.push(root->left);
// root = root->right;
// if (root == NULL && !st.empty()) {
// root = st.top();
// st.pop();
// }
// }
// while (root) {
// res.push_back(root->val);
// st.push(root);
// if (root->right)
// root = root->right;
// else {
// root = NULL;
// while (!st.empty() && !st.top()->left)
// st.pop();
// if (!st.empty()) {
// root = st.top()->left;
// st.pop();
// }
// }
// }
std::reverse(res.begin(), res.end());
return res;
}
};
Approach 3:
// Iteration.
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode *node = root;
while (node || !st.empty())
{
if (node)
{
st.push(node);
node = node->left;
}
else
{
node = st.top(); // Here the stack will not be empty.
TreeNode *right = node->right;
node->right = NULL;
if (!right)
{
st.pop();
res.push_back(node->val);
}
node = right;
}
}
return res;
}
};
// Iteration.
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
if (root)
st.push(root);
while (!st.empty())
{
TreeNode *node = st.top();
if (!node->left && !node->right)
{
res.push_back(node->val);
st.pop();
}
// else if (node->left)
// {
// st.push(node->left);
// node->left = NULL;
// }
// else if (node->right)
// {
// st.push(node->right);
// node->right = NULL;
// }
if (node->right)
{
st.push(node->right);
node->right = NULL;
}
if (node->left)
{
st.push(node->left);
node->left = NULL;
}
}
return res;
}
};