二叉树应用_重建二叉树

喜欢ヅ旅行 2022-05-22 02:37 171阅读 0赞

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{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) {}
     * };
     */
    
    TreeNode* reConstructBinaryTree(vector<int> preorder,vector<int> inorder)
    {
        if(preorder.size()<=0||inorder.size()<=0)
            return NULL;
    
        //前序遍历中的第一个节点，为根节点
        TreeNode*root=new TreeNode(preorder[0]);
        vector<int> left_preorder,left_inorder,right_preorder,right_inorder;
        int pos=0;
        for(;pos<inorder.size();++pos)
        {
            if(inorder[pos]==preorder[0])
                break;
            left_preorder.push_back(preorder[pos+1]);
            left_inorder.push_back(inorder[pos]);
        }
        pos++;
        for(;pos<inorder.size();++pos)
        {
            right_preorder.push_back(preorder[pos]);
            right_inorder.push_back(inorder[pos]);
        }
        root->left= reConstructBinaryTree(left_preorder,left_inorder);
        root->right= reConstructBinaryTree(right_preorder,right_inorder);
        return root;
    }