[LeetCode] Binary Tree Postorder Traversal

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

For example: Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

递归实现代码/****************************************************************** @Author : 楚兴* @Date: 2015/2/24 01:27* @Status : Accepted* @Runtime : 4 ms******************************************************************/struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL){}};class Solution {public: void helper(TreeNode *root, vector<int> &result) {if (root){helper(root->left, result);helper(root->right, result);result.push_back(root->val);}}vector<int> postorderTraversal(TreeNode *root) {vector<int> result;helper(root, result);return result;}};非递归实现代码1class Solution {public:vector<int> postorderTraversal(TreeNode *root) {vector<int> result;if (root == NULL){return result;}list<TreeNode*> nodes;TreeNode *p = root;TreeNode *cur;nodes.push_back(p);while(!nodes.empty()){cur = nodes.front();(cur->right == p || cur->left == p ||(cur->left == NULL && cur->right == NULL)){result.push_back(cur->val);nodes.pop_front();p = cur;}else{if (cur->right != NULL){nodes.push_front(cur->right);}if (cur->left != NULL){nodes.push_front(cur->left);}}}return result;}};非递归实现代码2class Solution {public:vector<int> postorderTraversal(TreeNode *root) {vector<int> result;stack<TreeNode*> nodes;TreeNode *p = NULL;TreeNode *cur = root;while(cur != NULL || !nodes.empty()){if (cur != NULL){while (cur != NULL){nodes.push(cur);cur = cur->left;}}else{cur = nodes.top();if (cur->right == NULL || cur->right == p){nodes.pop();p = cur;result.push_back(cur->val);cur = NULL;}else{cur = cur->right;}}}return result;}};

先序遍历的实现见博文Binary Tree Preorder Traversal

，你并不一定会从此拥有更美好的人生，