The problem:
Given a binary tree, return the postorder traversal of its nodes’ values. For example, given binary tree:
a 1
b / \
c 4 2
d \ /
e 10 3
return [10, 4, 3, 2, 1]
#include <iostream> #include <stack> #include <string> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x): val(x), left(nullptr), right(nullptr) {}; }; int postorderTraversal(TreeNode *root) { const TreeNode *p = root; stack<const TreeNode*> s; if(p!=nullptr) { TreeNode x(p->val); s.push(&x); if(p->right != nullptr) s.push(p->right); if(p->left != nullptr) s.push(p->left); } while(!s.empty()) { p = s.top(); s.pop(); if(p->left == nullptr && p->right == nullptr) printf("%d\n", p->val); else { TreeNode x(p->val); s.push(&x); if(p->right != nullptr) s.push(p->right); if(p->left != nullptr) s.push(p->left); } } return 0; } int main() { TreeNode root(1); TreeNode node1(2); TreeNode node2(3); TreeNode node3(4); TreeNode node4(10); root.left = &node3; root.right = &node1; node1.left = &node2; node3.right = &node4; postorderTraversal(&root); return 0; }
The similar code structure could be used for binary tree inorder traversal. The key idea here is to create a temporary node which holds only the value and push it into the stack. Whenever we meet a node without both childern, we print out its value.