The further application of Li Kou tree

654. The largest binary tree

Their thinking ：

1. Find the largest node in each layer .
2. The left and right subtrees are constructed layer by layer from bottom to top .

# 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 constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:

        if not nums: return

        n = nums.index(max(nums)) #  Find the current largest node 

        left = self.constructMaximumBinaryTree(nums[:n]) #  Use divide and conquer ,  Recursively construct left and right subtrees 
        right = self.constructMaximumBinaryTree(nums[n + 1:])

        root = TreeNode(nums[n], left, right) # Postorder traversal position , Build the tree layer by layer from the bottom up 
        return root

105. Construction of binary trees from traversal sequences of preorder and middle order

Their thinking ：

1. The first node in the preorder traversal sequence is the root node .
2. Use the index position of the root node in the middle order traversal order , Divide the pre order and middle order lists , Layer by layer recursion .

# 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 None
        
        root = TreeNode(preorder[0])
        #  Because there are no repeating elements , So you can find the position of the root node in the middle order traversal according to the value 
        midIndex = inorder.index(preorder[0])

        root.left = self.buildTree(preorder[1 :midIndex + 1], inorder[:midIndex])
        root.right = self.buildTree(preorder[midIndex + 1:], inorder[midIndex + 1:])

        return root

106. Construct binary tree from middle order and post order traversal sequence

Their thinking ：

1. The last node in the post order traversal sequence is the root node .
2. Use the index position of the root node in the middle order traversal order , Divide the post order and middle order lists , Layer by layer recursion .

# 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, inorder: List[int], postorder: List[int]) -> TreeNode:

        if not inorder or not postorder:
            return None

        root = TreeNode(postorder[-1])

        midIndex = inorder.index(postorder[-1])

        root.left = self.buildTree(inorder[:midIndex], postorder[:midIndex])
        root.right = self.buildTree(inorder[midIndex + 1:],	postorder[midIndex:-1])

        return root
        

889. Construct binary tree according to preorder and postorder traversal

Their thinking ：

1. The first node in the preorder traversal sequence is the root node , The last node in the post order traversal sequence is the root node .
2. Using preorder traversal , In the preorder traversal sequence , The second element is the index of the root node of the left subtree .
3. Use the position of the root node of the left subtree in the post order traversal , Split the pre order and post order arrays , Recursively build subtrees .

# 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 constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:
        
        if not preorder or not postorder:
            return None


        root = TreeNode(preorder[0])

        #  Because it's not looking for the root node , So you need to determine the length of the current part of the tree , If pre Is the length of the 1, Go straight back to root that will do 
        if len(preorder) == 1:
            return root
        
        midIndex = postorder.index(preorder[1]) #  The second element is the index of the root node of the left subtree .

        root.left = self.constructFromPrePost(preorder[1:midIndex+2], postorder[:midIndex+1])
        root.right = self.constructFromPrePost(preorder[midIndex+2:], postorder[midIndex+1:-1])

        return root