C/C++面试题—重建二叉树【前序 + 中序-> 重建二叉树和后序 + 中序 -> 重建二叉树】

悠悠 2022-05-24 06:09 158阅读 0赞

# 题目介绍 #

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

**题目来源于剑指offer，因为已经流传广泛，题目需要的是 前序 + 中序-> 重建二叉树，面试官很有可能会改题的，所有这里同时给出 `后序+ 中序 ->重建二叉树`的写法**。  
如果你看透问题的本质，也就十分好写了，因为 重建二叉树必须知道中序遍历结果，这样可以通过前/后序遍历 + 中序 -> 根节点 + 左右子树的范围，然后采用递归分治的思想就可以构建二叉树了。

# 代码展示 #

下面给出了输入参数为数组 和 输入参数为vector的写法。

/* 题目描述 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}， 则重建二叉树并返回。 */
    #include <iostream>
    #include <cstdlib>
    #include <vector>
    using namespace std;
    
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    
    };
    知道 前序 + 中序 -> 重建二叉树///
    TreeNode* TreeConstructCore(int* startPreOrder, int* endPreOrder, int* startInOrder, int* endInOrder);
    TreeNode* TreeConstruct(int* startPreOrder, int* startInOrder, int length)
    {
        if (startInOrder == nullptr || startPreOrder == nullptr || length <= 0)
            return nullptr;
        return TreeConstructCore(startPreOrder, startPreOrder + length - 1
            , startInOrder, startInOrder + length - 1);
    }
    TreeNode* TreeConstructCore(int* startPreOrder, int* endPreOrder, int* startInOrder, int* endInOrder)
    {
        TreeNode *root = new TreeNode(*startPreOrder);
        if (startPreOrder == endPreOrder)
        {
            if (startInOrder == endInOrder && *startPreOrder == *startInOrder)
                return root;
            else
                throw std::exception("invalid input");
        }
        //从找到中序遍历中的根结点
        int* rootInOrder = startInOrder;
        while (rootInOrder <= endInOrder && *rootInOrder != root->val)
            rootInOrder++;
        if (rootInOrder == endInOrder && *rootInOrder != root->val)
            throw std::exception("invalid input");
        int leftLen = rootInOrder - startInOrder;
        int* leftEndPreOrder = startPreOrder + leftLen;
        if (leftLen > 0)    //根结点有左子树，则构建左子树
            root->left = TreeConstructCore(startPreOrder + 1, leftEndPreOrder, startInOrder, rootInOrder - 1);
        if(leftLen < endInOrder - startInOrder) //存在右子树，则构建右子树
            root->right = TreeConstructCore(leftEndPreOrder + 1, endPreOrder, rootInOrder +1,endInOrder);
        return root;
    }
    知道 后序 + 中序 -> 重建二叉树///
    TreeNode* TreeConstructCore1(int* startPostOrder, int* endPostOrder, int* startInOrder, int* endInOrder);
    TreeNode* TreeConstruct1(int* startPostOrder, int* startInOrder, int length)
    {
        if (startInOrder == nullptr || startPostOrder == nullptr || length <= 0)
            return nullptr;
        return TreeConstructCore1(startPostOrder, startPostOrder + length - 1
            , startInOrder, startInOrder + length - 1);
    }
    TreeNode* TreeConstructCore1(int* startPostOrder, int* endPostOrder, int* startInOrder, int* endInOrder)
    {
        TreeNode *root = new TreeNode(*endPostOrder);
        if (startPostOrder == endPostOrder)
        {
            if (startInOrder == endInOrder && *endPostOrder == *startInOrder)
                return root;
            else
                throw std::exception("invalid input");
        }
        //从找到中序遍历中的根结点
        int* rootInOrder = startInOrder;
        while (rootInOrder <= endInOrder && *rootInOrder != root->val)
            rootInOrder++;
        if (rootInOrder == endInOrder && *rootInOrder != root->val)
            throw std::exception("invalid input");
        int leftLen = rootInOrder - startInOrder;
        int* leftEndPostOrder = startPostOrder + leftLen-1; //需要-1
        if (leftLen > 0)    //根结点有左子树，则构建左子树
            root->left = TreeConstructCore1(startPostOrder, leftEndPostOrder, startInOrder, rootInOrder - 1);
        if (leftLen < endInOrder - startInOrder)    //存在右子树，则构建右子树
            root->right = TreeConstructCore1(leftEndPostOrder + 1, endPostOrder-1, rootInOrder + 1, endInOrder);
        return root;
    }
    //二叉树的遍历，验证是否重建正确///
    void PreOrderBiTree(TreeNode* root)
    {
        if (nullptr == root)
            return;
        cout << root->val << " ";
        PreOrderBiTree(root->left);
        PreOrderBiTree(root->right);
    }
    void InOrderBiTree(TreeNode* root)
    {
        if (nullptr == root)
            return;
        InOrderBiTree(root->left);
        cout << root->val << " ";
        InOrderBiTree(root->right);
    }
    void PostOrderBiTree(TreeNode* root)
    {
        if (nullptr == root)
            return;
        PostOrderBiTree(root->left);
        PostOrderBiTree(root->right);
        cout << root->val << " ";
    }
    //vector容器写法，前序 + 中序 -> 重建二叉树
    class SolutionConstructBinaryTreeCore {
    public:
        TreeNode* reConstructBinaryTreeCore(vector<int>::iterator startPre, vector<int>::iterator endPre
            , vector<int>::iterator startIn, vector<int>::iterator endIn)
        {
            TreeNode *root = new TreeNode(*startPre);
    
            if (startPre == endPre) //没有左右孩子的结点，直接返回结点
            {
                if (startIn == endIn && *startPre == *startIn)
                    return root;
                else
                    throw std::exception("invalid input");
            }
            vector<int>::iterator rootIn = startIn; //在中序遍历中寻找根结点
            while (rootIn < endIn && *rootIn != root->val)
                rootIn++;
            if (rootIn < endIn && *rootIn != root->val)
                throw std::exception("invalid input");
    
            int leftLen = rootIn - startIn;
            vector<int>::iterator leftEndPre = startPre + leftLen;
            if (leftLen > 0)
                root->left = reConstructBinaryTreeCore(startPre + 1, leftEndPre, startIn, rootIn - 1);
            if (leftLen < endIn - startIn)
                root->right = reConstructBinaryTreeCore(leftEndPre + 1, endPre, rootIn + 1, endIn);
            return root;
        }
        TreeNode* reConstructBinaryTree(vector<int> preVec, vector<int> inVec) {
            //参数验证
            if (preVec.size() != inVec.size())
                return nullptr;
            int length = inVec.size();
            return reConstructBinaryTreeCore(preVec.begin(), preVec.begin() + length - 1, inVec.begin(), inVec.begin() + length - 1);
        }
    };
    
    int main(int argc, char *argv[])
    {
        //知道前序 + 中序 ->重建二叉树
        int preOrder[] = { 1, 2, 4, 7, 3, 5, 6, 8 };
        int inOrder[] = { 4, 7, 2, 1, 5, 3, 8, 6 };
        TreeNode* root = TreeConstruct(preOrder, inOrder, 8);
        cout << "前序 + 中序 ->重建二叉树" << endl;
        PreOrderBiTree(root); cout << endl;
        InOrderBiTree(root); cout << endl;
        PostOrderBiTree(root); cout << endl;
    
        //知道后序 + 中序 ->重建二叉树
        int postOrder[] = { 7, 4, 2, 5, 8, 6, 3, 1 };
        TreeNode* root1 = TreeConstruct1(postOrder, inOrder, 8);
        cout << "后序 + 中序 ->重建二叉树" << endl;
        PreOrderBiTree(root1); cout << endl;
        InOrderBiTree(root1); cout << endl;
        PostOrderBiTree(root1); cout << endl;
    
        //vector<int> preOrderVec = { 1, 2, 4, 7, 3, 5, 6, 8 };
        //vector<int> inOrderVec = { 4, 7, 2, 1, 5, 3, 8, 6 };
        //SolutionConstructBinaryTreeCore tree;
        //TreeNode* root2 = tree.reConstructBinaryTree(preOrderVec, inOrderVec);
        return 0;
    }

# 运行验证 #

![这里写图片描述][70]

[70]: /images/20220524/5f21a28616b249b8912e0ed606eda718.png