题解 | #实现二叉树先序，中序和后序遍历#

题目：实现二叉树先序，中序，后序的遍历

描述：分别按照二叉树先序，中序和后序打印所有的节点。

示例1：输入：{1,2,3}，返回值：[[1,2,3],[2,1,3],[2,3,1]]

解法一：

思路分析：既然题目中提到二叉树先序，中序，后序遍历，那么我们就先聊一聊关于一个二叉树的先序，中序，后序遍历。遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

二叉树的遍历主要有三种，括号内为其特点：

（1）先(根)序遍历（根左右）

（2）中(根)序遍历（左根右）

（3）后(根)序遍历（左右根）

就比如一个非常简单的二叉树{1，2，3}，它的图为

根据图分析可知，根节点为1，根节点的左子树为2，根节点的右子树为3，按照上图分析二叉树的遍历，先序遍历先访问根节点，再访问左子树，再访问右子树，所以其先序遍历为{1，2，3}，中序遍历为先访问左子树，再访问根节点，再访问右子树，所以其中序遍历结果为{2，1，3}，后序遍历为先访问左子树，再访问右子树，再访问根节点，故其后序遍历为{2，3，1}，根据上述逻辑，我们进行分析，在该题目中，我们可以采用递归的方法，首先设定三个存储的容器对象，分别为：pre，mid，post，其中每一个容器负责存储一个排序对象，然后按照递归序列进行分析即可得到最终的结果。

实例分析：输入：{1,2,3}

具体C++代码为：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<int> pre;
    vector<int> mid;
    vector<int> post;
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        if(root != nullptr){//nullptr任意指针类型
            preorder(root);
            midorder(root);
            postorder(root);
        }
        vector<vector<int>>res = {pre,mid,post};
        return res;
    }
    void preorder(TreeNode* root){//中左右
        if(root == NULL)
            return ;
        pre.push_back(root->val);//在Vector最后添加一个元素（参数为要插入的值）
        preorder(root->left);
        preorder(root->right);
    }
    void midorder(TreeNode* root){//左中右
        if(root == NULL)
            return;
        midorder(root->left);
        mid.push_back(root->val);
        midorder(root->right);
    }
    void postorder(TreeNode* root){//左右中
        if(root == NULL)
            return;
        postorder(root->left);
        postorder(root->right);
        post.push_back(root->val);
    }
};

因为具体要递归遍历树中的每一个元素三次，且最终要添加到res总的容器当中，所以其时间复杂度为O(N)，空间复杂度为O(N)。

解法二：

思路分析：上述采用递归实现判断，以下我们还可以通过非递归+栈的方式实现先序，中序，后序的遍历：

在先序中，首先需要借助栈来实现，压入顺序为根节点，右节点，左节点，出栈顺序对应为（根、左、右）。

在中序中，同样借助栈，进入循环的条件为栈是否为空或根节点是否为NULL，首先将左节点入栈，重复该过程，直到左节点不存在，然后依次出栈，出栈的同时判断当前节点的右节点是否存在，若存在则再次进入循环。

在后序遍历中，可以借助前序遍历，前序遍历为根左右，后序遍历为左右根，只需将前序遍历顺序调整为根右左，将最终结果reverse就可以得到后序遍历。

#include<stdio.h>
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<int> pre;
    vector<int> mid;
    vector<int> post;
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        if(root != nullptr){//nullptr任意指针类型
            preorder(root);
            midorder(root);
            postorder(root);
        }
        vector<vector<int>>res = {pre,mid,post};
        return res;
    }
    vector<int> preorder(TreeNode* root) {//中左右
        if(root==NULL){
            return pre;
        }
        stack<TreeNode*> tmp;//设置栈对象
        tmp.push(root);//保存根结点
        while(!tmp.empty()){
            auto x = tmp.top();
            tmp.pop();//出栈
            pre.push_back(x->val);//存入容器
            if(x->right){
                tmp.push(x->right);
            }
            if(x->left){
                tmp.push(x->left);
            }
        }
        return pre;
    }
    vector<int> midorder(TreeNode* root) {//左中右
        stack<TreeNode *> s;//设置栈对象
        while (s.size() || root){
            while (root){
                s.push(root);
                root = root->left;//先左
            }
            if (s.size()){
                root = s.top();
                s.pop();
                mid.push_back(root->val);
                root = root->right;
            }
        }
        return mid;
}
    vector<int> postorder(TreeNode* root) {//左右中
        if(root==NULL){
            return post;
        }
        stack<TreeNode*> tmp;//设置栈对象
        tmp.push(root);
        while(!tmp.empty()){
            auto x = tmp.top();
            tmp.pop();
            post.push_back(x->val);
            if(x->left){
                tmp.push(x->left);
            }
            if(x->right){
                tmp.push(x->right);
            }
        }
        reverse(post.begin(),post.end());
        return post;
    }
};