NC45 实现二叉树先序，中序和后序遍历

题意分析：

实现二叉树的先序，中序，后续遍历

题解一（递归遍历）：

比如有二叉树

图片说明

先序遍历：按照访问树根，左子树，右子树的顺序对树进行遍历，子树同样遵守这个遍历顺序

如图所示的二叉树：先序遍历结果为4,2,1,3,5.

代码实现如下：

void preOrder(TreeNode *root, vector<int> &ret) {
    if (!root) {
        return;
    }
    ret.push_back(root->val);
    preOrder(root->left, ret);
    preOrder(root->right, ret);
}

中序遍历：按照访问左子树，树根，右子树的顺序对树进行遍历，子树同样遵守这个遍历顺序

如图所示的二叉树：中序遍历结果为1,2,3,4,5.

代码实现如下：

void inOrder(TreeNode *root, vector<int> &ret) {
    if (!root) {
        return;
    }
    inOrder(root->left, ret);
    ret.push_back(root->val);
    inOrder(root->right, ret);
}

后序遍历：按照访问左子树，右子树，树根的顺序对树进行遍历，子树同样遵守这个遍历顺序

如图所示的二叉树：后序遍历结果为1,3,2,5,4.

代码实现如下：

void posOrder(TreeNode *root, vector<int> &ret) {
    if (!root) {
        return;
    }
    posOrder(root->left, ret);
    posOrder(root->right, ret);
    ret.push_back(root->val);
}

总结：那种遍历就表示什么时候访问根结点，先序表示首先访问根结点。中序表示在中间访问根结点

后序表示最后访问根节点。

三种遍历算法时间复杂度，n为树中结点个数。

空间复杂度：，h为树深。

题解二：（将递归用栈模拟）：

递归调用本质上都可以用栈进行模拟。

先序遍历的非递归展开：

vector<int> PreOrderNonRecur(TreeNode *root) {
    TreeNode *T = root;
    stack<TreeNode *> S;
    vector<int> ret;
    while (T || !S.empty()) {
        while (T) {
            ret.push_back(T->val);
            S.push(T);
            T = T->left;
        }
        if (!S.empty()) {
            T = S.top();
            S.pop();
            T = T->right;
        }
    }
    return ret;
}

中序遍历的非递归展开：

vector<int> inOrderNonRecur(TreeNode *root) {
    TreeNode *T = root;
    stack<TreeNode *> S;
    vector<int> ret;
    while (T || !S.empty()) {
        while (T) {
            S.push(T);
            T = T->left;
        }
        if (!S.empty()) {
            T = S.top();
            S.pop();
            ret.push_back(T->val);
            T = T->right;
        }
    }
    return ret;
}

后序遍历的非递归展开：

后序遍历有点特殊，其访问顺序为左子树-右子树-根，可以利用栈，依次将根-右子树-左子树压栈，在弹出的时候就有这个顺序。先序遍历的顺序为根-左子树-右子树，只要将先序遍历的非递归展开左右先后顺序，最后输出栈中的元素即可。

vector<int> posOrderNonRecur(TreeNode *root) {
    TreeNode *T = root;
    stack<TreeNode *> S1;
    stack<TreeNode *> S2;
    while (T || !S1.empty()) {
        while (T) {
            S2.push(T);
            S1.push(T);
            T = T->right;
        }
        if (!S1.empty()) {
            T = S1.top();
            S1.pop();
            T = T->left;
        }
    }
    vector<int> ret;
    while (!S2.empty()) {
        ret.push_back(S2.top()->val);
        S2.pop();
    }
    return ret;
}

三种遍历算法时间复杂度，n为树中结点个数。

空间复杂度：，h为树深。