Given a binary tree, return the postorder traversal of its nodes' values.
=>给定一个二叉树，给出后序遍历的所有节点值
For example:
=>例如
Given binary tree {1,#,2,3},
=>给定一个二叉树{1，#，2,3}
1
\
2
/
3
return [3,2,1].
=>返回[3,2,1]
Note: Recursive solution is trivial, could you do it iteratively
=》注意：递归的实现很普通，能不能不用递归实现？
在CODE上查看代码片派生到我的代码片
/**
* 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 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出来哦。
代码实现：
在CODE上查看代码片派生到我的代码片
/**
* 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 postorderTraversal(TreeNode *root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
stack TreeStack;
vector 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;
}
};
执行结果：
67 / 67test cases passed.
Status:
Accepted
Runtime: 16 ms
希望大家有更好的算法能够提出来，不甚感谢。