二叉树的前序、中序、后序遍历

这里记录下二叉树的三种非递归DFS遍历方式。遍历过程中，均使用了stack这一数据结构。

1. 前序(pre-order)

先访问根节点，由于是stack，先push右节点然后再左节点。

vector<int> PreorderTraversal(TreeNode* root){
    vector<int> ret;
    if(root == nullptr){
        return ret;
    }

    stack<TreeNode*> nodes;
    nodes.push(root);
    while(!nodes.empty()){
        TreeNode* cur = nodes.top();
        nodes.pop();
        ret.push_back(cur->val);
        if(cur->right)
            nodes.push(cur->right);
        if(cur->left)
            nodes.push(cur->left);
    }

    return ret;
}

2. 中序(in-order)

不断dfs根节点的左子树直到为null，然后push栈顶，再不断dfs栈顶的右子树。

vector<int> InorderTraversal(TreeNode* root){
    vector<int> ret;
    if(root==nullptr)
        return ret;
    
    TreeNode* cur = root;
    stack<TreeNode*> nodes;
    while(cur!=nullptr || !nodes.empty()){
        while(cur!=nullptr){
            nodes.push(cur);
            cur = cur->left;
        }

      cur = nodes.top();
      nodes.pop();
      ret.push_back(cur->val);
      cur = cur->right;
    }
    
    return ret;
}

3.后序(post-order)

思路与前序有些类似，但最终结果需要逆序。
先访问根节点，然后访问右子树，最后左子树，最终对结果逆序。

vector<int> PostorderTraversal(TreeNode* root){
    vector<int> ret;
    if(root == nullptr)
        return ret;

    stack<TreeNode*> nodes;
    nodes.push(root);
    while(!nodes.empty()){
        TreeNode* cur = nodes.top();
        ret.push_back(cur->val);
        if(cur->left)
            nodes.push(cur->left);
        if(cur->right)
            nodes.push(cur->right);
    }

    reverse(ret.begin(), ret.end());
    return ret;
}