[问题描述]
Given a binary tree, return the postorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1
2
/
3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
非递归实现二叉树后续遍历
[解题思路]
说明：网络上好多相关的方法，但是基本上都使用的O(n)的空间来记录节点是否已经访问过，所以我再次特地列举此题算法，需要O(stack) + O(1) 空间复杂度
如果栈顶元素的孩子节点是刚刚访问过的节点，那么就说明孩子节点已经访问结束，出栈！
1 std::vector<int> Solution::postorderTraversal(TreeNode *root) 2 { 3 std::vector<int> ans; 4 std::stack<TreeNode*> pathStack; 5 if (root == NULL) 6 return ans; 7 TreeNode *post = root; 8 pathStack.push(root); 9 while (!pathStack.empty()){ 10 TreeNode* tmp = pathStack.top(); 11 if (tmp->left == post || tmp->right == post || (tmp->left == NULL && tmp->right == NULL)){ 12 ans.push_back(tmp->val); 13 pathStack.pop(); 14 post = tmp; 15 } 16 else{ 17 if (tmp->right != NULL) pathStack.push(tmp->right); 18 if (tmp->left != NULL) pathStack.push(tmp->left); 19 } 20 } 21 }
leetcode -- Binary Tree Postorder Traversal,布布扣,bubuko.com
leetcode -- Binary Tree Postorder Traversal
原文：http://www.cnblogs.com/taizy/p/3912902.html