给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。示例 1:输入:preorder [3,9,20,15,7], inorder [9,3,15,20,7]输出:[3,9,20,null,null,15,7]思路速记前序首元素定根中序劈成左右两半前序按长度切分对应左右左右递归建树class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) - Optional[TreeNode]: if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) root.left self.buildTree(preorder[1:idx1], inorder[:idx]) root.right self.buildTree(preorder[idx1:], inorder[idx1:]) return root
LeetCode热题100-从前序与中序遍历序列构造二叉树
给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。示例 1:输入:preorder [3,9,20,15,7], inorder [9,3,15,20,7]输出:[3,9,20,null,null,15,7]思路速记前序首元素定根中序劈成左右两半前序按长度切分对应左右左右递归建树class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) - Optional[TreeNode]: if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) root.left self.buildTree(preorder[1:idx1], inorder[:idx]) root.right self.buildTree(preorder[idx1:], inorder[idx1:]) return root
