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

二叉树的遍历整体上是分成两种的，一种是递归的方式，一种是非递归的方式。

前序遍历的递归方式：

      根据每个节点的步骤来，先输出当前节点的值，再去管左子节点、最后再管右子节点。
      递归的方法有个特点就是，只需要考虑当前步骤该做什么，下一步应该往哪走，即可。

    void Pre(TreeNode* root){
        if(root!=nullptr)
        {
            cout <<root->val;
            Pre(root->left);
            Pre(root->right);
        }
    }

前序遍历的非递归方式：

      前序遍历的非递归方式是相对比较简单的，因为是从根节点开始，优先输出当前节点的值，再去管左子节点和右子节点。
      这里我们取一个栈，将root节点先存入初始化的栈中，然后设定循环条件是，栈不为空，每次取栈顶节点的值，再将栈顶节点的右子节点和左子节点依次压入栈中。
     （这里考虑非空并且由于栈的后入先出特性）

void Pre(TreeNode* root){
        stack<TreeNode*> res;
        res.push(root);
        while(!res.empty()){
            TreeNode* temp = res.top();
            res.pop();
            cout << temp->val;
            if(temp->right)
                res.push(temp->right);
            if(temp->left)
                res.push(temp->left);
        }
    }

中序遍历的递归方式：

       递归的方式总的来说大同小异，只是每个步骤的逻辑处理顺序不一样。

 void Ord(TreeNode* root){
        if(root!=nullptr)
        {
            Ord(root->left);
            cout << root->val;
            Ord(root->right);
        }
    }

中序遍历的非递归方式：

      这里其实就比较复杂了，因为我们在当前节点的处理，是优先当前节点的左子节点。不用递归的话，我们怎么样才能实现每个节点处理时，都优先处理
      左子节点呢？优先输出左子节点，那就把从根节点开始左子节点依次入栈，那这样压栈完毕后，出栈的第一个必定是根节点左子树的最深的左子节点。
      接着我们在查看当前出栈的右子节点是否为空，如果不为空便在输出当前节点的值之后将其入栈。整体代码如下。

void Ord(TreeNode* root){
        stack<TreeNode*> res;
        TreeNode* temp = root;
        while(temp||!res.empty()){
            while(temp)
            {
                res.push(temp);
                temp = temp->left;
            }
            if(!res.empty())
            {
                temp = res.top();
                res.pop();
                cout << temp->val ;
                temp = temp->right;
            }
        }
    }

后序遍历的递归方式：

  同上递归。

void Post(TreeNode* root){
        if(root!=nullptr)
        {
            Post(root->left);
            Post(root->right);
            cout << root->val;
        }
    }

后序遍历的非递归方式：

        取一个栈作为临时存储栈，由于栈的先进后出特性，所以得先把当前节点的右子节点先入栈，再将左子节点再入栈。

void Post(TreeNode* root){
        TreeNode* temp = root;
        stack<TreeNode*> res;
        stack<TreeNode*> tempres;
        while (temp || !tempres.empty()) {
            if (temp) {
                tempres.push(temp);//
                res.push(temp);
                temp = temp->right;
            }
            else {                  
                    temp = tempres.top();
                    tempres.pop();
                    temp = temp->left;
                }
            }
        while(!res.empty()){
                    post.push_back(res.top()->val);
                    res.pop();
        }
}