[数据结构与算法]medium 剑指 Offer 重建二叉树 递归（分治）

递归（分治）：

c++

public/private的函数都调用的成员变量,需要放在public函数外，写在public一个函数里，private函数不能调用

class Solution {
public:
    unordered_map<int, int> index; // public/private的函数都调用的成员变量,需要放在public函数外，写在public一个函数里，private函数不能调用

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        if(n==0){
            return nullptr;
        }
        
        for (int i = 0; i < n; i++) {
            index[inorder[i]] = i;  // 中序遍历中的值->在中序遍历中的位置
        }
        // 前序遍历的长度[0, n-1], 中序遍历的长度[0, n-1]
        return rebuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
    
private:
    TreeNode* rebuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){  // 传入前序/中序遍历长度
        // 递归出口
        if (preorder_left > preorder_right) {
            return nullptr;
        }

        int preorder_root = preorder_left;  // 前序遍历的第1个点是根, 前序遍历根位置preorder_left
        // preorder[位置] = 值, index[值] = 序号  // 该根(值)在中序遍历中的位置已经保存在index字典中
        int inorder_root = index[preorder[preorder_root]];  // 中序遍历根位置inorder_root

        TreeNode* root = new TreeNode(preorder[preorder_root]);  // 建立新树(新根),树中放入根的值
        int size_left_subtree = inorder_root - inorder_left;  // 左树的长度

        // 递归 传入
        // 左树在原始前序遍历中的位置:[preorder_left + 1, preorder_left + size_left_subtree]
        // 左树在原始中序遍历中的位置:[inorder_left, inorder_root - 1]
        root->left = rebuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 右树在原始前序遍历中的位置:[preorder_left + size_left_subtree + 1, preorder_right]
        // 右树在原始中序遍历中的位置:[inorder_root + 1, inorder_right]
        root->right = rebuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);

        return root;
    }
};

public的多个函数都调用的成员变量,需要放在public函数外，写在public一个函数里，public其他函数不能调用

class Solution {
public:
    unordered_map<int, int> index; // public/private的函数都调用的成员变量,需要放在public函数外，写在public一个函数里，private函数不能调用

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        if(n==0){
            return nullptr;
        }
        
        for (int i = 0; i < n; i++) {
            index[inorder[i]] = i;  // 中序遍历中的值->在中序遍历中的位置
        }
        // 前序遍历的长度[0, n-1], 中序遍历的长度[0, n-1]
        return rebuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* rebuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){  // 传入前序/中序遍历长度
        // 递归出口
        if (preorder_left > preorder_right) {
            return nullptr;
        }

        int preorder_root = preorder_left;  // 前序遍历的第1个点是根, 前序遍历根位置preorder_left
        // preorder[位置] = 值, index[值] = 序号  // 该根(值)在中序遍历中的位置已经保存在index字典中
        int inorder_root = index[preorder[preorder_root]];  // 中序遍历根位置inorder_root

        TreeNode* root = new TreeNode(preorder[preorder_root]);  // 建立新树(新根),树中放入根的值
        int size_left_subtree = inorder_root - inorder_left;  // 左树的长度

        // 递归 传入
        // 左树在原始前序遍历中的位置:[preorder_left + 1, preorder_left + size_left_subtree]
        // 左树在原始中序遍历中的位置:[inorder_left, inorder_root - 1]
        root->left = rebuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 右树在原始前序遍历中的位置:[preorder_left + size_left_subtree + 1, preorder_right]
        // 右树在原始中序遍历中的位置:[inorder_root + 1, inorder_right]
        root->right = rebuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);

        return root;
    }
};

python

index = {element: i for i, element in enumerate(inorder)}  # 字典赋键对值

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: # 已定义TreeNode
        def reBuildTree(preorder_left, preorder_right, inorder_left, inorder_right):
            if preorder_left > preorder_right:
                return None

            preorder_root = preorder_left  # 前序遍历的第1个点是根, 前序遍历根位置preorder_left
            inorder_root = index[preorder[preorder_root]]  # 中序遍历根位置inorder_root

            root = TreeNode(preorder[preorder_root]) # 建立新树(class TreeNode),树中放入根的值
            size_left_subtree = inorder_root - inorder_left  # 左树的长度

            # 递归 传入
            # 左树在原始前序遍历中的位置:[preorder_left + 1, preorder_left + size_left_subtree]
            # 左树在原始中序遍历中的位置:[inorder_left, inorder_root - 1]
            root.left = reBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)

            # 右树在原始前序遍历中的位置:[preorder_left + size_left_subtree + 1, preorder_right]
            # 右树在原始中序遍历中的位置:[inorder_root + 1, inorder_right]
            root.right = reBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)

            return root
        
        n = len(preorder)
        if n==0:
            return None
        
        index = {}  # index = {element: i for i, element in enumerate(inorder)} 字典赋键对值
        for i in range(n):
            index[inorder[i]] = i;  # 中序遍历中的值->在中序遍历中的位置
        
        return reBuildTree(0, n - 1, 0, n - 1);