一、题目介绍
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3
输出: [3,2,1] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、解题思路
本题同样采用迭代的方法解决，同样利用栈来实现。访问右子树时，需要注意其是否访问过，所以需要增加变量进行记录，详细见代码。
三、解题代码
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> vec;
if(root == NULL)
return vec;
stack<TreeNode*> st;
TreeNode* pTemp = root;
TreeNode* preNode = NULL;
while(pTemp || !st.empty())
{
while(pTemp)
{
st.push(pTemp);
pTemp = pTemp->left;
}
pTemp = st.top();
//右节点为空，或者右节点已经被访问
if(pTemp->right == NULL || pTemp->right == preNode)
{
vec.push_back(pTemp->val);
st.pop();
preNode = pTemp;
pTemp = NULL;
}
else
{
pTemp = pTemp->right;
preNode = NULL;
}
}
return vec;
}
};
四、解题结果
