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

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

Input: preorder [3,9,20,15,7], inorder [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:

Input: preorder [-1], inorder [-1]
Output: [-1]

来源 力扣 LeetCode
链接 https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权 非商业转载请注明出处。

确定根节点的值 把根节点做出来 然后递归构造左右子树。

方法1 python

# 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:
 def bulid(preorder,prestart,preend,inorder,instart,inend):
 flag 0
 if prestart preend: return 
 #找根及索引
 rootvar preorder[prestart]
 for i in range(instart,inend 1):
 if rootvar inorder[i]:
 flag i
 break
 #找左右子树的长度
 leftsize flag-instart
 root TreeNode(rootvar)
 root.left bulid(preorder,prestart 1,prestart leftsize,inorder,instart,flag-1)
 root.right bulid(preorder,prestart leftsize 1,preend,inorder,flag 1,inend)
 return root
 return bulid(preorder,0,len(preorder)-1,inorder,0,len(inorder)-1)

方法2 java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val val;
 * this.left left;
 * this.right right;
class Solution {
 public TreeNode buildTree(int[] preorder, int[] inorder) {
 return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
 public TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
 if (preStart preEnd) {
 return null;
 // 根节点
 int rootVal preorder[preStart];
 // 找到根节点在中序遍历中的索引
 int index 0;
 for (int i 0; i inorder.length; i ) {
 if (rootVal inorder[i]) {
 index i;
 break;
 int leftSize index - inStart;
 // 递归构造左右子树
 TreeNode root new TreeNode(rootVal);
 root.left build(preorder, preStart 1, preStart leftSize, inorder, inStart, index - 1);
 root.right build(preorder, preStart leftSize 1, preEnd, inorder, index 1, inEnd);
 return root;