二叉树的重建--读书笔记02

痛定思痛。 2021-12-04 02:37 172阅读 0赞

## 读书笔记02------二叉树的重建 ##

链接：[https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6][https_www.nowcoder.com_questionTerminal_8a19cbe657394eeaac2f6ea9b0f6fcf6]  
来源：牛客网

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{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) { 
            int len=pre.size();
            //递归深度
            if(len<=0) { 
                return nullptr;
            }
            //创建一个根节点,根节点的value就是前序遍历的第一个数字
            TreeNode* root=new TreeNode(pre[0]);
            //根节点在中序遍历中的位置
            int rootvin=0;
            for(int i=0;i<len;++i) { 
                if(vin[i]==pre[0]) { 
                    rootvin=i;
                    break;
                }
            }
            //把数据保存在容器中,后续进行递归
            vector<int> pre_left,pre_right,vin_left,vin_right;
            for(int i=0;i<rootvin;++i) { 
                pre_left.push_back(pre[i+1]);//前序的第一个数为根节点,故从后一个位置开始
                vin_left.push_back(vin[i]);
            }
            for(int i=rootvin+1;i<len;++i) { 
                pre_right.push_back(pre[i]);
                vin_right.push_back(vin[i]);
            }
            //开始递归创建树
            root->left=reConstructBinaryTree(pre_left,vin_left);
            root->right=reConstructBinaryTree(pre_right,vin_right);
            return root;
        }
    };

[https_www.nowcoder.com_questionTerminal_8a19cbe657394eeaac2f6ea9b0f6fcf6]: https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6