leetcode Binary Tree Postorder Traversal(二)
* };
*/
class Solution {
public:
vector postorderTraversal(TreeNode *root) {
vector res;
TreeNode *prev = NULL, *cur = NULL;
stack s;
if (root != NULL)
s.push(root);
while (!s.empty()) {
cur = s.top();
if (prev == NULL || prev->left == cur || prev->right == cur) {
if (cur->left)
s.push(cur->left);
else if (cur->right)
s.push(cur->right);
}
else if (cur->left == prev && cur->right)
s.push(cur->right);
else {
res.push_back(cur->val);
s.pop();
}
prev = cur;
}
return res;
}
};