binary-tree-postorder-traversa题解
binary-tree-postorder-traversal
http://www.nowcoder.com/questionTerminal/32af374b322342b68460e6fd2641dd1b
我的方法是使用一个栈，由于后序遍历，因此先将右节点入栈，再将左节点入栈；然后每次判断栈顶元素，如果栈顶元素是叶子节点，则说明它要么是左节点，要么是右节点；这时候就需要判断栈顶元素的前一个元素是否为栈顶节点的爸，如果是栈顶节点的爸的话，就需要连带着他爸一起弹出；而如果是左节点的话，只需弹出他自己即可。
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> result;
if(!root) return result;
stack<TreeNode *> s;
s.push(root);
while(!s.empty()){
TreeNode * temp = s.top();
if(!temp->left && !temp->right){
result.push_back(temp->val);
s.pop();
TreeNode *t = s.top();
while(!s.empty() && (t->left || t->right) && (t->left == temp || t->right == temp)){
temp = t;
result.push_back(t->val);
s.pop();
t = s.top();
}
}
else{
if(temp -> right) s.push(temp->right);
if(temp -> left) s.push(temp->left);
}
}
return result;
}
}; 
农夫山泉工作强度 11人发布