[LeetCode] Binary Tree Postorder Traversal

本文主要是介绍[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;}
};

非递归实现代码1

class 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();//①当前结点不是叶子结点，但是孩子已经遍历过。//②当前结点是叶子结点if (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;}
};

非递归实现代码2

class 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;}
};