劍指offer【7】：重構二叉樹，遞歸思路

思路：最終是要重構二叉樹；

1. 确定子樹的根節點：遞歸（目前子樹根在前序中的索引，left，right）每層傳入根節點在前序周遊的索引；在中序周遊中拿到根節點的索引，建立 目前子樹的根節點

2. 确定目前子樹的左節點：遞歸（左子樹的根節點在前序索引, left, 目前根在中序索引-1）

3. 确定目前子樹的右節點：遞歸（右子樹的根節點在前序索引, 目前根在中序索引+1, right）

其他：為了友善查詢中序中節點的索引，建立map(節點:idx)

建立遞歸思路：

遞歸結束：子樹的左邊界idx > 子樹右邊界

遞推過程：目前遞歸層建立root

傳回：傳回目前層根節點作為上一層的左或右節點

class Solution:
    # 思路：最終是要重構二叉樹；
    #   1. 确定子樹的根節點：遞歸（目前子樹根在前序中的索引，left，right）每層傳入根節點在前序周遊的索引；在中序周遊中拿到根節點的索引，建立目前子樹的根節點
    #   2. 确定目前子樹的左節點：遞歸（左子樹的根節點在前序索引, left, 目前根在中序索引-1）
    #   3. 确定目前子樹的右節點：遞歸（右子樹的根節點在前序索引, 目前根在中序索引+1, right）
    #   其他：為了友善查詢中序中節點的索引，建立map(節點:idx)
    #   建立遞歸思路：
    #       遞歸結束：子樹的左邊界idx > 子樹右邊界
    #       遞推過程：目前遞歸層建立root
    #       傳回：傳回目前層根節點作為上一層的左或右節點
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        
        self.pre, self.map_in= preorder, {}
        for i in range(len(inorder)): # 給中序建立索引
            self.map_in[inorder[i]] = i
        return self.recur(0, 0, len(inorder)-1)

    def recur(self, root_idx_pre, left, right):
            if left > right:
                return
            root = TreeNode(self.pre[root_idx_pre])  # 建立目前子樹的根節點
            root_idx_in = self.map_in[self.pre[root_idx_pre]]
            root.left = self.recur(root_idx_pre+1, left, root_idx_in-1)
            root.right = self.recur(root_idx_in - left + root_idx_pre + 1, root_idx_in+1, right)
            return root  # 傳回根節點作為上一層的左或右節點