【剑指offer】先序、中序遍历结果重建二叉树

小鱼儿 2022-07-12 02:57 109阅读 0赞

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

--------------------

#include <iostream>
    #include <vector>
    #include <stack>
    
    using namespace std;
    
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    //创建二叉树算法
    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> mid)
    {
        int nodeSize = mid.size();
        if (nodeSize == 0)
            return NULL;
    
        vector<int> leftPre, leftMid, rightPre, rightMid;
        TreeNode* phead = new TreeNode(pre[0]); //第一个当是根节点
    
        int rootPos = 0;  //根节点在中序遍历中的位置
        for (int i = 0; i < nodeSize; i++)
        {
            if (mid[i] == pre[0])
            {
                rootPos = i;
                break;
            }
        }
    
        for (int i = 0; i < nodeSize; i++)
        {
            if (i < rootPos)
            {
                leftMid.push_back(mid[i]);
                leftPre.push_back(pre[i + 1]);
            }
            else if (i > rootPos)
            {
                rightMid.push_back(mid[i]);
                rightPre.push_back(pre[i]);
            }
    
        }
    
        phead->left = reConstructBinaryTree(leftPre, leftMid);
        phead->right = reConstructBinaryTree(rightPre, rightMid);
    
        return phead;
    }
    
    //打印后续遍历顺序
    void printNodeValue(TreeNode* root)
    {
        if (!root){
            return;
        }
        printNodeValue(root->left);
        printNodeValue(root->right);
        cout << root->val<< " ";
    }
    
    int main()
    {
        vector<int> preVec{ 1, 2, 4, 5, 3, 6 };
        vector<int> midVec{ 4, 2, 5, 1, 6, 3 };
        cout << "先序遍历序列为 1 2 4 5 3 6" << endl;
        cout << "中序遍历序列为 4 2 5 1 6 3" << endl;
    
        TreeNode* root = reConstructBinaryTree(preVec, midVec);
    
        cout << "后续遍历序列为 ";
        printNodeValue(root);
        cout << endl;
        system("pause");
    }
    
    /*
    测试二叉树形状：
               1
        2             3 
     4    5        6
    */

--------------------

运行结果：

先序遍历序列为 1 2 4 5 3 6
    中序遍历序列为 4 2 5 1 6 3
    后续遍历序列为 4 5 2 6 3 1
    请按任意键继续. . .