【树】前序，中序，后序的非递归遍历

树其实是递归定义的，所以递归遍历树的方式也是比较自然的。但是因为种种原因---比如面试官想测你智商---你必须采用非递归的方法遍历树，那么请记住以下两个诀窍：

1. 树的非递归遍历是对递归遍历的模仿，而怎么模仿递归呢？使用栈和循环

2. 都只需要一个循环

下面是code，都通过了leetcode的测试：

/*前序遍历*/
vector<int> preorderTraversal(TreeNode *root){
        vector<int> result;
        if(root!=NULL){
            stack<TreeNode *> s;
            bool done=false;
            TreeNode * current = root;
            while(!done){
                if(current!=NULL){
                    s.push(current);
                    result.push_back(current->val);
                    current=current->left;
                }
                else{
                    if(s.empty()){
                        done=true;
                    }
                    else{
                        current=s.top();
                        s.pop();
                        current=current->right;
                    }
                }
            }
        }
        return result;
    }
/*中序遍历*/
vector<int> inorderTraversal(TreeNode *root){
        vector<int> result;
        if(root!=NULL){
            stack<TreeNode *> s;
            bool done=false;
            TreeNode * current = root;
            while(!done){
                if(current!=NULL){
                    s.push(current);

                    current=current->left;
                }
                else{
                    if(s.empty()){
                        done=true;
                    }
                    else{
                        current=s.top();
                        result.push_back(current->val);
                        s.pop();
                        current=current->right;
                    }
                }
            }
        }
        return result;
    }
/*后序遍历*/
vector<int> postorderTraversal(TreeNode *root) {
        stack<TreeNode *> s;
        vector<int> result;
        if(root!=NULL){
            s.push(root);
            while(!s.empty()){
                TreeNode * current=s.top();
                s.pop();
                result.push_back(current->val);
                if(current->left!=NULL)
                    s.push(current->left);
                if(current->right!=NULL)
                    s.push(current->right);
            }
        }
        reverse(result.begin(), result.end());
        return result;
    }