【剑指Offer】（树）重建二叉树

分手后的思念是犯贱 2022-03-16 00:57 211阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_8a19cbe657394eeaac2f6ea9b0f6fcf6_tpId_13_tqId_11157_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

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

#### 解决方法 ####

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { 
            return createTree(pre,vin);
        }
        TreeNode* createTree(vector<int> pre, vector<int> vin){ 
            if (pre.empty() || vin.empty() || pre.size()!=vin.size()) return nullptr; 
            //[1]前序遍历第一个节点为当前数的根节点
            int rootVal=pre[0];
            TreeNode *root=new TreeNode(rootVal);
            //[2]在中序遍历中找到根节点所在的位置
            int index=0;
            for(int i=0;i<vin.size();i++){ 
                if (vin[i]==rootVal){ 
                    index=i;
                    break;
                }
            }
            //[3]递归的构建左子树和右子树
            //(注意：end()指向的是最后一个元素的下一个位置，所以30行pre.begin()+index+1处不能是pre.begin()+index)
            root->left=createTree(vector<int>(pre.begin()+1,pre.begin()+index+1),vector<int>(vin.begin(),vin.begin()+index));
            root->right=createTree(vector<int>(pre.begin()+index+1,pre.end()),vector<int>(vin.begin()+index+1,vin.end()));
            return root;
        }
    };

[https_www.nowcoder.com_practice_8a19cbe657394eeaac2f6ea9b0f6fcf6_tpId_13_tqId_11157_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking