题解 | #重建二叉树#

第十三题 递归调用 通过先序遍历和中序遍历 还原树

学习 截取容器的片段 和找容器的指定位置

/**
 * 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) {
        if(pre.size() == 0 )
            return NULL;
        
        // pre的第一个点 先序遍历的第一个点 永远是数的子树的根节点
        TreeNode *ret_ans = new TreeNode(pre[0]);
        // 退出递归调用的条件是只有一个结点
        if(pre.size() == 1)
            return ret_ans;
        
        // 找到中序遍历的根节点所在的位置
        auto point = find(vin.begin(), vin.end(), pre[0]) ;
        // 左子树的长度是 点所在位置减开头
        int left_len=point-vin.begin();
        // 右子树的长度是 总长度减点所在的位置
        int right_len=vin.end()-point;
        
        // 递归调用 将左子树 的两次遍历传入
        // 两个容器 第一个为pre 删掉根节点的左半部分
        // 第二个为vin删掉根节点的左半部分
        TreeNode* lefttree = reConstructBinaryTree(vector<int>(pre.begin() + 1, pre.begin() + 1 + left_len),vector<int>(vin.begin(),vin.begin()+left_len));

        // 递归调用 将右子树 的两次遍历传入
        // 第一个为 删掉根节点的pre的有半部分
        // 第二个为 删掉根节点的vin的右半部分
        TreeNode* righttree = reConstructBinaryTree(vector<int>(pre.begin() + 1 +left_len, pre.end()),vector<int>(vin.begin()+left_len+1,vin.end()));
        
        // 将结果 接入当前的子树 并返回
        ret_ans->left=lefttree;
        ret_ans->right=righttree;
        return ret_ans;

    }
};