Binary Tree Postorder Traversal, Hard (?) Leetcode problem
Problem is here: https://leetcode.com/problems/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]
Follow up: Recursive solution is trivial, could you do it iteratively?
The recursive solution is indeed trivial and I don't really think this should be considered a hard problem. Solution is below, cheers, Boris.
public class Solution
{
public IList PostorderTraversal(TreeNode root)
{
List list = new List();
PostorderTraversal(root, list);
return list;
}
private void PostorderTraversal(TreeNode root, IList list)
{
if (root == null) return;
PostorderTraversal(root.left, list);
PostorderTraversal(root.right, list);
list.Add(root.val);
}
}
The reason it's marked as "hard" is because of the follow-up that asks to implement the solution iteratively :) I wouldn't say it makes the problem really hard, but certainly requires a bit more thought.
ReplyDeleteC++ solution is below:
class Solution {
public:
vector postorderTraversal(TreeNode* root) {
if (!root) return {};
stack s; s.push(root);
vector traversal;
while (!s.empty()) {
auto node = s.top(); s.pop();
traversal.push_back(node->val);
if (node->left) s.push(node->left);
if (node->right) s.push(node->right);
}
reverse(traversal.begin(), traversal.end());
return traversal;
}
};
Cheers,
Taras
I realized that, but since it was a follow-up, it came across as bonus :)
ReplyDeletewell, as long as judge accepts the solution, I don't think it can be considered wrong :) Maybe they should have tried to reduce the memory and time constraints to fail recursive solutions...
Delete