We have talked about the Pre-order in this post, and In-order Traversal for binary tree in this post. And this article talks about the third kind: Postorder traversal, which is to display the root/current node after recursively calling into postOrder function for its left sub tree and right sub tree respectively.
Recursion
Slightly modifying the display order gives a post-order traversal.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> r; if (root == NULL) { return r; } vector<int> x; auto left = postorderTraversal(root->left); if (left.size()) { x.insert(x.end(), left.begin(), left.end()); } auto right = postorderTraversal(root->right); if (right.size()) { x.insert(x.end(), right.begin(), right.end()); } x.push_back(root->val); return x; } }; |
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> r;
if (root == NULL) {
return r;
}
vector<int> x;
auto left = postorderTraversal(root->left);
if (left.size()) {
x.insert(x.end(), left.begin(), left.end());
}
auto right = postorderTraversal(root->right);
if (right.size()) {
x.insert(x.end(), right.begin(), right.end());
}
x.push_back(root->val);
return x;
}
};Iterative using Stack
If we use a stack to push the left sub tree first, right sub tree next, the right sub tree will be dealt first, However, we need to append the node in the reverse order.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> r; stack<TreeNode*> st; if (root) { st.push(root); } while (!st.empty()) { auto p = st.top(); st.pop(); r.insert(r.begin(), p->val); if (p->left) { st.push(p->left); } if (p->right) { st.push(p->right); } } return r; } }; |
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> r;
stack<TreeNode*> st;
if (root) {
st.push(root);
}
while (!st.empty()) {
auto p = st.top();
st.pop();
r.insert(r.begin(), p->val);
if (p->left) {
st.push(p->left);
}
if (p->right) {
st.push(p->right);
}
}
return r;
}
};You would use r.push_back(p->val) however you would need to reverse the r at the end.
1 / \ 2 3
We visit the nodes in the order of 1 – 3 – 2. But the postorder traversal should be 2 – 3 – 1, which is the reverse.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: C++ Coding Exercise - Binary Tree Preorder Traversal
Next Post: C/C++ Coding Exercise - Find the Duplicate Number
