LeetCode: Binary Tree Traversal
题目：树的先序和后序。
后序地址：https://oj.leetcode.com/problems/binary-tree-postorder-traversal/
先序地址：https://oj.leetcode.com/problems/binary-tree-preorder-traversal/
后序算法：利用栈的非递归算法。初始时，先从根节点一直往左走到底，并把相应的元素进栈；在循环里每次都取出栈顶元素，如果该栈顶元素的右子树在上一次已经访问到，则将该元素存入vector中，并且记录下上一次访问的元素，否则，往右走一步，然后在一直往左走到底，并把相应的元素进栈。一直循环，直到栈顶结束。代码：
/**
* 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) {
vector<int> result;
if(!root) return result;
TreeNode *p = root;
stack<TreeNode*> stk;
while(p){
stk.push(p);
p = p->left;
}
TreeNode *pre = NULL;
while(!stk.empty()){
p = stk.top();
if(!p->right || p->right == pre){
pre = p;
result.push_back(p->val);
stk.pop();
}else{
p = p->right;
while(p){
stk.push(p);
p = p->left;
}
}
}
return result;
}
};
先序算法：利用栈的非递归算法。初始时，先从根节点一直往左走到底，并且把相应的元素进栈，以及把相应的元素存入vector。在循环里，每次取出栈顶元素，然后出栈一个元素，如果有右子树的话，往右走，然后一直往左走到底，并且把相应的元素进栈，以及把相应的元素存入vector。一直循环，直到栈为空。代码：
/**
* 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> preorderTraversal(TreeNode *root) {
vector<int> result;
if(!root) return result;
stack<TreeNode*> stk;
TreeNode *p = root;
while(p){
result.push_back(p->val);
stk.push(p);
p = p->left;
}
while(!stk.empty()){
p = stk.top();
stk.pop();
if(p->right){
p = p->right;
while(p){
result.push_back(p->val);
stk.push(p);
p = p->left;
}
} }
return result;
}
};