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

Difficulty

Medium

法1

思路

前序数组preorder的第一个值cur_val = preorder[0]为根节点。中序数组inorder里面cur_val前面的为根节点左边的，令in_left = inorder[0:cur_idx]。 中序数组inorder里面cur_val右边的为该根节点右边的，令in_right = inorder[cur_idx+1:]。在前序数组preorder里面，紧挨着cur_val的len(in_left) 个元素亦是根节点左边的。在前序数组preorder里面，最后的len(in_right) 个元素是根节点右边的。

新形成的 in_left pre_left 和 in_right, pre_right 分别是该根节点的左子树和右子树的中序、前序。于是，新的一层递归就可以开始了

递归终止条件为前序的数组小于2，因为小于2了就可以确定一颗子树，没必要继续递归了，这时，返回该子树的根节点，作为上一层的左子树或者右子树。

所以递归层与层之间的联系为当前层的左右节点由下一层返回。

题解


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder) == 0:
            return
        elif len(preorder) == 3:
            node = TreeNode(preorder[0])
            node.left = inorder[0]
            node.right = inorder[2]
            return node
        elif len(preorder) == 2:
            node = TreeNode(preorder[0])
            if preorder[0] == inorder[0]: #前序和中序一样，所以子节点在右边
                node.left = inorder[1]
            else:
                node.right = inorder[0]
            return node
        elif len(preorder) == 1:
            node = TreeNode(preorder[0])
            return node
        

        cur_root = preorder[0]
        in_left = inorder 中 cur_root 前面的
        in_right = inorder 中 cur_root 后面的

        pre_left =  preorder[1: len(in_left)]
        pre_right = preorder[:-len(in_right)]
        root.left = self.buildTree(pre_left, in_left)
        root.right = self.buildTree(pre_right, in_right)
        return root

该进：发现上面的代码基线条件有问题


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # 基线条件
        if len(preorder) <= 2:
            if len(preorder) == 2:
                node = TreeNode(preorder[0])
                if preorder[0] == inorder[0]: # 说明子节点在右边
                    node.right = inorder[1]
                    return node
                else: # 说明子节点在左边
                    node.left = inorder[0]
                return node
            elif len(preorder) == 1:
                return TreeNode(preorder[0])
            else:
                return None

        cur_root = preorder[0]
        # 查找cur_root在inorder中的索引
        cur_idx = inorder.index(cur_root)
        # in_left = inorder 中 cur_root 前面的
        # in_right = inorder 中 cur_root 后面的
        in_left = inorder[0:cur_idx]
        in_right = inorder[cur_idx:]

        pre_left =  preorder[1: len(in_left)+1]
        pre_right = preorder[-len(in_right):]

        root = TreeNode(cur_root)
        root.left = self.buildTree(pre_left, in_left)
        root.right = self.buildTree(pre_right, in_right)
        return root

最终版本：


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # 基线条件
        if len(preorder) <= 2:
            if len(preorder) == 2:
                node = TreeNode(preorder[0])
                if preorder[0] == inorder[0]: # 说明子节点在右边
                    node.right = TreeNode(inorder[1])
                    return node
                else: # 说明子节点在左边
                    node.left = TreeNode(inorder[0])
                return node
            elif len(preorder) == 1:
                return TreeNode(preorder[0])
            elif len(preorder) == 0:
                return None
				# 当前子树根节点
        cur_root = preorder[0]
        # 查找cur_root在inorder中的索引
        cur_idx = inorder.index(cur_root)
        # in_left = inorder 中 cur_root 前面的
        # in_right = inorder 中 cur_root 后面的
        in_left = inorder[0:cur_idx]
        pre_left =  preorder[1: len(in_left)+1]
        if cur_idx == len(inorder)-1: # 防止cur_idx 越界
            in_right = []
            pre_right = []
        else:
            in_right = inorder[cur_idx+1:]
            pre_right = preorder[-len(in_right):]
        
        root = TreeNode(cur_root)
        root.left = self.buildTree(pre_left, in_left)
        root.right = self.buildTree(pre_right, in_right)
        return root

实际上对列表进行切片时，如果下标超过列表长度，不会报错，只会返回一个空列表，所以不用防止越界。且进一步优化基线条件。最终代码如下


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(inorder) == 0:
            return None
        if len(inorder) == 1:
            return TreeNode(preorder[0])

        curVal = preorder[0]
        curIdx = inorder.index(curVal)

        in_left = inorder[0:curIdx]
        in_right = inorder[curIdx+1:]

        pre_left = preorder[1:len(in_left)+1]
        pre_right = preorder[-len(in_right):]

        curNode = TreeNode(curVal)
        curNode.left = self.buildTree(pre_left, in_left)
        curNode.right = self.buildTree(pre_right, in_right)
        return curNode