从前序与中序遍历序列构造二叉树-leetcode

题目描述

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

解法一

思路：

采用递归方法，先序遍历第一个节点是根节点，在中序遍历中可以找到根节点的左右子树节点范围。

在先序遍历中最后一个左子树节点序号为x。

x-preLeft-1=pIndex-1-inLeft

x=pIndex-inLeft+preLeft

代码：

/*** 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 build(int[] preorder, int preLeft, int preRight,Map<Integer,Integer> map,int inLeft,int inRight) {if(preLeft > preRight||inLeft>inRight) return null;int rootVal=preorder[preLeft];TreeNode root = new TreeNode(rootVal);int pIndex= map.get(rootVal);root.left=build(preorder,preLeft+1,pIndex-inLeft+preLeft,map,inLeft,pIndex-1);root.right=build(preorder,pIndex-inLeft+preLeft+1,preRight,map,pIndex+1,inRight);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {int preLen=preorder.length;int inLen=inorder.length;if(preLen!=inLen) return null;Map<Integer,Integer> map=new HashMap<>();for(int i=0;i<inLen;i++){map.put(inorder[i],i);}return build(preorder,0,preLen-1,map,0,inLen-1);}
}