Binary Tree Postorder Traversal-二叉树的后序遍历

本文主要是介绍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].

=>返回[3,2,1]

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

=》注意：递归的实现很普通，能不能不用递归实现？

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
}
};

晓东解析：

其实之前晓东已经和大家分析了前序遍历的实现，后序遍历相对而言要复杂一点，关键的思想在于，我如何知道我已经遍历了右子树，所以，需要增加一个类似的标志位，来标志右子树的遍历。因此，我们先遍历到左子树，然后遍历右子树，加上一个标志位，在右子树已经遍历的情况下，就可以把该节点加入了。还有一点需要注意的是，在加入节点的时候才能把该节点从stack中pop出来哦。

代码实现：

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
stack<TreeNode*> TreeStack;
vector<int> result;
TreeNode * Hasvisited;
if(root == NULL) return result;
while(root || !TreeStack.empty()){
while(root){
TreeStack.push(root);
root = root->left;
}
root = TreeStack.top();
if(root->right == NULL || Hasvisited == root->right){
result.push_back(root->val);
Hasvisited = root;
TreeStack.pop();
root = NULL;
}
else{
root = root->right;
}
}
return result;
}
};

执行结果：