LeetCode-105-从前序与中序遍历序列构造二叉树

原题链接： https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

根据一棵树的前序遍历与中序遍历构造二叉树。

image.png

解题思路：

1. 同题：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
2. 根据前序遍历的特性，前序list的首位即为根节点，并在中序list中寻找该节点，左边[9]即为根节点的左子树，右边[15,20,7]即为根节点的左子树， 因此维护一个词典，存储中序遍历的val->idx。

Python3代码：

# 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:
        def helper(left, right):
            if left > right:
                return None
            
            # 前序遍历的第一位即root
            val = preorder.pop(0)
            root = TreeNode(val)

            # 构建左子树
            root.left = helper(left, idx_map[val]-1)
            # 构建右子树
            root.right = helper(idx_map[val]+1, right)
            return root 

        idx_map = {val:idx for idx, val in enumerate(inorder)}
        return helper(0, len(inorder)-1)