Problem:
Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},
|
1 2 3 4 5 |
1 \ 2 / 3 |
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
Solution 1:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> ans; postorderTraversal(root, ans); return ans; } void postorderTraversal(TreeNode* root, vector<int>& ans) { if (!root) return; postorderTraversal(root->left, ans); postorderTraversal(root->right, ans); ans.push_back(root->val); } }; |
Solution 2:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: vector<int> postorderTraversal(TreeNode* root) { if (!root) return {}; vector<int> ans; const vector<int> l = postorderTraversal(root->left); const vector<int> r = postorderTraversal(root->right); ans.insert(ans.end(), l.begin(), l.end()); ans.insert(ans.end(), r.begin(), r.end()); ans.push_back(root->val); return ans; } }; |
Solution 3:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: vector<int> postorderTraversal(TreeNode* root) { if (!root) return {}; deque<int> ans; stack<TreeNode*> s; s.push(root); while (!s.empty()) { TreeNode* n = s.top(); s.pop(); ans.push_front(n->val); // O(1) if (n->left) s.push(n->left); if (n->right) s.push(n->right); } return vector<int>(ans.begin(), ans.end()); } }; |