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

一、105. 从前序与中序遍历序列构造二叉树 1.1、题目描述

1.2、题解 1.2.1、递归

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not inorder:
            return
        # 前序遍历，第一个节点是根节点
        root = TreeNode(preorder.pop(0))
        # 在中序遍历， 根节点分割左右子树
        i = inorder.index(root.val)
        
        root.left = self.buildTree(preorder, inorder[:i])
        root.right = self.buildTree(preorder, inorder[i+1:])
        return root

二、106. 从中序与后序遍历序列构造二叉树 2.1、题目描述

2.2、题解 2.2.1、递归

class Solution:
	# 中序遍历：左节点 -> 根节点 -> 右节点
	# 后序遍历：左节点 -> 右节点 -> 根节点
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder:
            return
        if len(inorder) == 1:
            return TreeNode(inorder[0])
        # 在后序遍历中：最后一个节点为根节点
        root = TreeNode(postorder[-1])
        
        i = inorder.index(root.val)
        # 在中序遍历中：根节点左侧为该树的左子树，右侧为该树的右子树
        root.left = self.buildTree(inorder[:i], postorder[:i])
        # 注意postorder[i:len(postorder)-1]， 最后一个节点为根节点，已经使用，长度需要-1
        root.right = self.buildTree(inorder[i+1:], postorder[i:len(postorder)-1])
        
        return root

三、1008. 先序遍历构造二叉树 3.1、题目描述

3.2、题解 3.2.1、二叉搜索树，前序遍历排序就是中序遍历， 此题就变成了105. 从前序与中序遍历序列构造二叉树

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        # 二叉搜索树 preorder排序就是 中序遍历
        inorder = sorted(preorder)
        # 这就变成了105. 从前序与中序遍历序列构造二叉树
        return self.buildTree(preorder, inorder)
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not inorder:
            return
        # 前序遍历，第一个节点是根节点
        root = TreeNode(preorder.pop(0))
        # 在中序遍历， 根节点分割左右子树
        i = inorder.index(root.val)
        
        root.left = self.buildTree(preorder, inorder[:i])
        root.right = self.buildTree(preorder, inorder[i+1:])
        return root

    def dfs(self, preorder: List[int], start: int, end: int) -> TreeNode:
        # 先序遍历，第一个数值是根节点
        rootVal = preorder[0]
        root = TreeNode(rootVal)
        idx = start
        for i in range(start+1, end):
            if preorder[i] > rootVal:
                idx = i
                break;
        print(start, idx, end)
        if start  TreeNode:
        return self.dfs(preorder, 0, len(preorder)-1)
        
    def dfs(self, preorder: List[int], start: int, end: int) -> TreeNode:
        if start > end:
            return None
        # 先序遍历，第一个数值是根节点
        rootVal = preorder[start]
        root = TreeNode(rootVal)
        if start == end:
            return root

        print(start, end)
        idx = start+1
        while preorder[idx] = len(preorder): break;
        
        root.left = self.dfs(preorder, start+1, idx-1)
        root.right = self.dfs(preorder, idx, end)
        return root