【Leetcode】105: 从前序与中序遍历序列构造二叉树

【Leetcode】105: 从前序与中序遍历序列构造二叉树

 

 这题目是有一个常见的套路的,由于先序遍历的结果list都会遵循这样的一个排列方式,也就是第一个是root,后面的分别是左子树的node的集合,以及右子树的node的集合。

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

而inorder中序遍历的结果则是:

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

画成下图就可以表示为:

【Leetcode】105: 从前序与中序遍历序列构造二叉树

 

 

我们通过preorder拿到root的地址之后,就可以找到root在inorder当中的位置。然后拿到preorder和inorder当中的左子树和右子树,这样就可以对root.left以及root.right进行递归,build出一棵完整的二叉树。

代码如下:

# 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 not preorder or not inorder:  # 递归终止条件
            return
        root = TreeNode(preorder[0])  
        idx = inorder.index(preorder[0])  
        
        root.left = self.buildTree(preorder[1:1 + idx], inorder[:idx])
        root.right = self.buildTree(preorder[1 + idx:], inorder[idx + 1:])
        return root

 

上一篇:leetcode 重建二叉树


下一篇:leetcode 105 从前序与中序遍历序列构造二叉树