leetcode -- tree 2

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]: 
        if not nums:
            return None
        m_index = nums.index(max(nums))
        root = TreeNode(nums[m_index])
        root.left = self.constructMaximumBinaryTree(nums[:m_index])
        root.right = self.constructMaximumBinaryTree(nums[m_index + 1 :])
        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 not preorder:
            return None

        # 首先创建一个栈 载入前序序列的第一个节点
        root = TreeNode(preorder[0])
        inorderindex = 0
        stack = [root]

        # 整体遍历前序遍历的数组
        for i in range(1, len(preorder)):
            p_val = preorder[i]
            node = stack[-1]


            if node.val != inorder[inorderindex]:
                node.left = TreeNode(val=p_val)
                stack.append(node.left)
            else:
                while stack and stack[-1].val == inorder[inorderindex]:
                    node = stack.pop()
                    inorderindex += 1
                node.right = TreeNode(val=p_val)
                stack.append(node.right)

        return root
# 递归写法
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None
        
        index = inorder.index(preorder[0])
        root = TreeNode(preorder[0])
        root.left = self.buildTree(preorder[1: index + 1], inorder[0: index])
        root.right = self.buildTree(preorder[index + 1:], inorder[index + 1:])
        return root

# 递归
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if inorder == [] or postorder == []:
            return 
        index = inorder.index(postorder[-1])
        root = TreeNode(postorder[-1],
                        self.buildTree(inorder[:index], postorder[:index]),
                        self.buildTree(inorder[index + 1:], postorder[index:-1]))
        return root

# 迭代
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not postorder:
            return None

        root = TreeNode(postorder[-1])
        stack = [root]
        i_inorder = -1

        for i in range(1, len(postorder)):
            p_val = postorder[-1 - i]
            node = stack[-1]

            if node.val != inorder[i_inorder]:
                node.right = TreeNode(p_val)
                stack.append(node.right)
            else:
                while stack and stack[-1].val == inorder[i_inorder]:
                    i_inorder -= 1
                    node = stack.pop()
                node.left = TreeNode(p_val)
                stack.append(node.left)
        
        return root

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        elif len(preorder) == 1:
            return TreeNode(preorder[0])
        
        root = TreeNode(preorder[0])
        if preorder[1] == postorder[-2]:
            root.left = self.constructFromPrePost(preorder[1:], postorder[:-1])
        else:
            post_index = postorder.index(preorder[1])
            pre_index = preorder.index(postorder[-2])

            root.left = self.constructFromPrePost(preorder[1: pre_index],postorder[:post_index + 1])
            root.right = self.constructFromPrePost(preorder[pre_index:],postorder[post_index + 1:-1]) 
        return root

class Codec:

    def serialize(self, root):
        # Encodes a tree to a single string.
        def dfs(node):
            if not node:
                res.append('None')
            else:
                res.append(str(node.val))
                dfs(node.left)
                dfs(node.right)
            
        res = []
        dfs(root)
        return '[' + ','.join(res) + ']'

    def deserialize(self, data):
        # Decodes your encoded data to tree.
        def dfs():
            v = next(i)
            if v == 'None':
                return None
            node = TreeNode(int(v))
            node.left = dfs()
            node.right = dfs()
            return node
        i = iter(data[1:-1].split(','))
        return dfs()

# 层序遍历

class Codec:
    from collections import deque

    def serialize(self, root):
        # Encodes a tree to a single string.
        if not root:
            return '[]'
        res = []
        tmp = deque([root])    
        while tmp:
            node = tmp.popleft()
            if not node:
                res.append('None')
            else:
                res.append(str(node.val))
                tmp.append(node.left)
                tmp.append(node.right)

        return '[' + ','.join(res) + ']'

    def deserialize(self, data):
        # Decodes your encoded data to tree.
        if data == '[]':
            return None
        i, v = 1, data[1:-1].split(',')
        root = TreeNode(int(v[0]))
        tmp = deque([root])
        while tmp:
            node = tmp.popleft()
            if v[i] != 'None':
                node.left = TreeNode(int(v[i]))
                tmp.append(node.left)
            
            i += 1
            if v[i] != 'None':
                node.right = TreeNode(int(v[i]))
                tmp.append(node.right)
            i += 1

        return root