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]
Follow up: Recursive solution is trivial, could you do it iteratively?
Similar Questions:
// OJ: https://leetcode.com/problems/binary-tree-postorder-traversal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
private:
vector<int> ans;
void dfs(TreeNode* root) {
if (!root) return;
dfs(root->left);
dfs(root->right);
ans.push_back(root->val);
}
public:
vector<int> postorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};// OJ: https://leetcode.com/problems/binary-tree-postorder-traversal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> s;
TreeNode *prev = NULL;
while (root || s.size()) {
while (root) {
s.push(root);
root = root->left;
}
root = s.top();
if (!root->right || root->right == prev) {
ans.push_back(root->val);
s.pop();
prev = root;
root = NULL;
} else root = root->right;
}
return ans;
}
};