本文主要是介绍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},
1\2/3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
二叉树的后序遍历
递归算法：
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int>res;if(root==NULL) return res;return postorder(root,res);}vector<int> postorder(TreeNode* root,vector<int>& res){if(root){postorder(root->left,res);postorder(root->right,res);res.push_back(root->val);}return res;}
};迭代算法：
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int>res;if(root==NULL) return res;stack<TreeNode*> qu;TreeNode* node=root;while(!qu.empty()||node){if(node){qu.push(node);res.push_back(node->val);node=node->right;}else{TreeNode* cur=qu.top();qu.pop();node=cur->left;}}reverse(res.begin(),res.end());return res;}
};总结
先序、中序、后序均可用递归、迭代实现。
递归：
先序： 输出节点->pre函数(left)->pre函数(right)
中序：inorder函数(left)->输出节点->inorder函数(right)
后序：postorder函数(left)->postorder函数(right)->输出节点
迭代：
用栈实现；
先序：输出栈顶元素，加入栈顶元素右节点->加入栈顶元素左节点->输出栈顶元素.依次循环。
中序：读取根节点->将左节点全部加入栈->输出栈顶元素->加入栈顶元素右节点->将左节点全部加入栈.依次循环。
后序：读取根节点->加入根节点的所有右边节点（加入一次读取一次，也就是输出该元素）->出栈->加入栈顶元素左节点(输出该元素)->加入该节点所有右边节点（加入一次读取一次，也就是输出该元素）。最后翻转输出序列，就是后序遍历的迭代算法。比较难一点。
本文列出了后序遍历的递归以及迭代算法。先序和中序请参考
http://blog.csdn.net/sinat_24520925/article/details/45603147
http://blog.csdn.net/sinat_24520925/article/details/45621865
这篇关于leetcode--Binary Tree Postorder Traversal的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
