145. Binary Tree Postorder Traversal
1. Description
Given the root of a binary tree, return the postorder traversal of its nodes' values.
2. Example
Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Example 4:
Input: root = [1,2]
Output: [2,1]
Example 5:
Input: root = [1,null,2]
Output: [1,2]
3. Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
4. Follow Up
- Recursive solution is trivial, could you do it iteratively?
5. Solutions
My Accepted Solution(Follow Up)
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// vector<int> postorderTraversal(TreeNode* root)
vector<int> postorderTraversal(TreeNode *i_root)
{
vector<int> result;
if(i_root == nullptr) return result;
stack<TreeNode *> nodes{{i_root}};
for(auto previous = i_root; !nodes.empty(); )
{
auto iter = nodes.top();
if((!iter->left && !iter->right) || iter->left == previous || iter->right == previous)
{
result.push_back(iter->val);
nodes.pop();
previous = iter;
}
else
{
if(iter->right) nodes.push(iter->right);
if(iter->left) nodes.push(iter->left);
}
}
return result;
}
};
5.1 Reverse Preorder Traversal(Follow Up)
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
// preorder: root left right
// if we change the order into: root right left
// then, we reverse the order, it will be left rigt root, which is postorder
class Solution
{
public:
// vector<int> postorderTraversal(TreeNode* root)
vector<int> postorderTraversal(TreeNode *i_root)
{
vector<int> result;
if(i_root == nullptr) return result;
stack<TreeNode *> nodes;
nodes.push(i_root);
for(TreeNode *iter; !nodes.empty(); )
{
iter = nodes.top();
nodes.pop();
result.push_back(iter->val);
if(iter->left) nodes.push(iter->left);
if(iter->right) nodes.push(iter->right);
}
reverse(result.begin(), result.end());
return result;
}
};
5.2 Reverse Preorder Traversal - With Assit Node(Follow Up)
n is the number of nodes in i_root
Time complexity: O(n)
Space complexity: O(n)
// preorder: root left right
// if we change the order into: root right left
// then, we reverse the order, it will be left rigt root, which is postorder
class Solution
{
public:
// vector<int> postorderTraversal(TreeNode* root)
vector<int> postorderTraversal(TreeNode *i_root)
{
vector<int> result;
if(i_root == nullptr) return result;
stack<TreeNode *> nodes;
for(auto iter = i_root; iter || !nodes.empty(); )
{
if(iter)
{
result.push_back(iter->val);
nodes.push(iter);
iter = iter->right;
}
else
{
iter = nodes.top();
nodes.pop();
iter = iter->left;
}
}
reverse(result.begin(), result.end());
return result;
}
};