Leetcode 145 Solution

This article provides solution to leetcode question 145 (binary-tree-postorder-traversal)

https://leetcode.com/problems/binary-tree-postorder-traversal

Solution

/** * 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) { stack<std::pair<TreeNode*, int>> s; vector<int> res;
if (root == NULL) return res;
s.push(make_pair(root, 0));
while (s.empty() == false) { auto pair = s.top(); s.pop();
auto node = pair.first; int stage = pair.second;
if (node == NULL) continue;
if (stage == 0) { s.push(make_pair(node, 1)); s.push(make_pair(node->left, 0)); } else if (stage == 1) { s.push(make_pair(node, 2)); s.push(make_pair(node->right, 0)); } else if (stage == 2) { res.push_back(node->val); } }
return res; } };