程序员代码面试指南 3.1：实现二叉树先序、中序和后序遍历

模板题，注意简单的建树方法。

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

//建立二叉树
void createTree(TreeNode* root, int& n)
{
    if (n == 0) return;

    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left, -- n);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right, -- n);
    }
}

//前序递归遍历
void preOrderRecursion(TreeNode* root, vector<int>& res)
{
    if (root == nullptr) return;

    res.push_back(root->val);
    preOrderIteration(root->left, res);
    preOrderIteration(root->right, res);
}

//前序迭代遍历
void preOrderIteration(TreeNode* root, vector<int>& res)
{
    stack<TreeNode*> stk;
    stk.push(root);

    while (!stk.empty())
    {
        TreeNode* node = stk.top();
        stk.pop();

        res.push_back(node->val);
        if (node->right) stk.push(node->right); //栈是先进后出，所以右节点先进
        if (node->left) stk.push(node->left);
    }
}

//中序递归遍历
void inOrderRecursion(TreeNode* root, vector<int>& res)
{
    if (root == nullptr) return;

    inOrderIteration(root->left, res);
    res.push_back(root->val);
    inOrderIteration(root->right, res);
}

//中序迭代遍历
void inOrderIteration(TreeNode* root, vector<int>& res)
{
    stack<TreeNode*> stk;
    TreeNode* p = root;

    while (p != nullptr || !stk.empty())
    {
        if (p != nullptr)       //先一直往左子树走
        {
            stk.push(p);
            p = p->left;
        }
        else                    //左子树没有了，回退同时往右子树走
        {
            p = stk.top();
            stk.pop();

            res.push_back(p->val);
            p = p->right;
        }
    }
}

//后序递归遍历
void postOrderRecursion(TreeNode* root, vector<int>& res)
{
    if (root == nullptr) return;

    postOrderIteration(root->left, res);
    postOrderIteration(root->right, res);
    res.push_back(root->val);
}

//后序迭代遍历
void postOrderIteration(TreeNode* root, vector<int>& res)
{
    stack<TreeNode*> stk;
    stk.push(root);

    while (!stk.empty())
    {
        TreeNode* node = stk.top();
        stk.pop();

        res.push_back(node->val);
        if (node->left) stk.push(node->left);
        if (node->right) stk.push(node->right);
    }

    reverse(res.begin(), res.end());    //最后要翻转
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode* root = new TreeNode(rootVal);
    createTree(root, n);

    vector<int> res;

    //preOrderIteration(root, res);
    preOrderRecursion(root, res);
    for (int &node : res) cout << node << " ";
    cout << endl;
    res.clear();

    //inOrderIteration(root, res);
    inOrderRecursion(root, res);
    for (int &node : res) cout << node << " ";
    cout << endl;
    res.clear();

    //postOrderIteration(root, res);
    postOrderRecursion(root, res);
    for (int &node : res) cout << node << " ";
    cout << endl;
    res.clear();

    return 0;
}