105. 从前序与中序遍历序列构造二叉树 [medium]

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

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

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

通过次数92,463 | 提交次数137,271

First Try

2020-07-09

preorder为root + left + right， inorder为left + root + right
通过preorder的root确认了inorder的root，也确认了inorder的left和right
preorder和inorder右侧的right都相等，既然inorder的left+root长度确认，preorder的root + left的长度也就确定了
剩下的就是递归了，还有判断终止条件。不得不说pythonlist切片的方便，就算某个边界超出了范围，也只是返回一个空集，并不会导致错误。

可惜自己摸索的时候在画图上出现了错乱，这道套路题花了许多时间.

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

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        # 刚好也作为终止条件的判断
        if not len(preorder):
            return None 
        # print(preorder, inorder)
        root = preorder[0]
        idx_inorder_root = inorder.index(root)
        root = TreeNode(root)
        root.left = self.buildTree(preorder[1: idx_inorder_root + 1], inorder[: idx_inorder_root])
        root.right = self.buildTree(preorder[idx_inorder_root + 1:], inorder[idx_inorder_root + 1: ])
        return root 

执行用时：132 ms, 在所有 Python 提交中击败了81.19%的用户
内存消耗：87.1 MB, 在所有 Python 提交中击败了11.11%的用户

failed try

超时且换乱的写法, 没有把握到完整的规律。

只知道preorder第一位为root，inorder在root的左侧为left node,但是如何判断preorder的左侧和右侧陷入了混乱之中。

没有注意到preorder为root + left + right， inorder为left + root + right, 因此确认了inorder的root，右侧的right都相等，preorder的root + left的长度也就确定了。

# 超时且换乱的写法
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not len(preorder):
            return None 
        
        def rebuild(preorder, inorder):
            if not len(preorder):
                return None 
            root = preorder[0]
            inorder_root_idx = inorder.index(root)
            preorder_left_idx = inorder_root_idx
            root = TreeNode(root)
            if inorder_root_idx != 0:
                # print("left", root.val, preorder, inorder_root_idx,inorder)
                left_inorder = inorder[0: inorder_root_idx]
                # 结果超时了。。。
                left_preorder = [e for e in preorder if e in left_inorder]
                # bug写法
                # preorder_left_idx = preorder.index(inorder[inorder_root_idx - 1])
                # left_preorder = preorder[1: preorder_left_idx + 1]
                root.left = rebuild(left_preorder, left_inorder)
            if inorder_root_idx != len(inorder) - 1:
                right_inorder = inorder[inorder_root_idx + 1:]
                right_preorder = preorder[preorder_left_idx + 1:]
                root.right = rebuild(right_preorder, right_inorder)
            return root 
        return rebuild(preorder, inorder)

105. 从前序与中序遍历序列构造二叉树 [medium]​

First Try​

105. 从前序与中序遍历序列构造二叉树 [medium]

First Try