Binary Tree Postorder Traversal
http://www.lintcode.com/en/problem/binary-tree-postorder-traversal/
Solution
Recursion.
- 访问左子树
- 访问右子树
- 输出根
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
// write your code here
vector<int> result;
postorder(root, result);
return result;
}
void postorder(TreeNode *root, vector<int> &result) {
if(root == NULL)
return;
postorder(root->left, result);
postorder(root->right, result);
result.push_back(root->val);
}
};
Iteration.
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
// write your code here
stack<TreeNode*> mystk;
vector<int> result;
if(root == NULL)
return result;
mystk.push(root);
TreeNode*cur, *pre;
cur = root;
pre = root;
while (!mystk.empty()) {
cur = mystk.top();
if((cur->left == NULL && cur->right == NULL) || cur->right==pre
|| cur->left==pre) {
mystk.pop();
result.push_back(cur->val);
pre = cur;
} else {
if(cur->right)
mystk.push(cur->right);
if(cur->left)
mystk.push(cur->left);
}
}
}
};
Morrise traversal O(1) space
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
// write your code here
vector<int> res;
TreeNode dummy(INT_MIN);
dummy.left = root;
TreeNode *curr = &dummy;
while (curr) {
if (!curr->left) {
curr = curr->right;
} else {
TreeNode *node = curr->left;
while (node->right && node->right != curr) {
node = node->right;
}
if (!node->right) {
node->right = curr;
curr = curr->left;
} else {
vector<int> v = trace_back(curr->left, node);
res.insert(res.end(), v.begin(), v.end());
node->right = nullptr;
curr = curr->right;
}
}
}
return res;
}
vector<int> trace_back(TreeNode *frm, TreeNode *to) {
vector<int> res;
TreeNode *curr = frm;
while (curr != to) {
res.emplace_back(curr->val);
curr = curr->right;
}
res.emplace_back(to->val);
reverse(res.begin(), res.end());
return res;
}
};