LintCode(68) Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes' values.

Have you met this question in a real interview? 

Yes

Example

Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Challenge

Can you do it without recursion?

最头疼了，比那尼玛word ladder还难理解。。干脆贴个答案吧，碰到就听天由命了。。。

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

class Solution { public: vector<int> postorderTraversal(TreeNode *root) { vector<int> result; stack<TreeNode *> myStack; TreeNode *current = root, *lastVisited = NULL; while (current != NULL || !myStack.empty()) { while (current != NULL) { myStack.push(current); current = current->left; } current = myStack.top(); if (current->right == NULL || current->right == lastVisited) { myStack.pop(); result.push_back(current->val); lastVisited = current; current = NULL; } else { current = current->right; } } return result; } };