AlgoPressAppearance
0105-从前序与中序遍历序列构造二叉树
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
示例 1: 
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]
提示:
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- -3000 <= preorder[i], inorder[i] <= 3000
- preorder 和 inorder 均无重复元素
- inorder 均出现在 preorder
- preorder 保证为二叉树的前序遍历序列
- inorder 保证为二叉树的中序遍历序列
思路
前序遍历的输出顺序是 根节点，左子树，右子树 中序遍历的输出顺序是 左子树，根节点，右子树 所以我们根据输出特性，先从前序节点中取出第一个元素构造为根节点，然后从中序遍历中找出根节点的位置，将中序的左边递归构造为根节点的左子树 将中序的右边递归构造为根节点的右子树，这样递归到最后完毕
参考代码
csharp
public class Solution {
Dictionary<int,int> dict = new Dictionary<int,int>();
private TreeNode BuildNode(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd){
if(preorderStart>preorderEnd){
return null;
}
int rootValue = preorder[preorderStart];
TreeNode node = new TreeNode(rootValue);
int inorderIndex = dict[rootValue];
int offset = inorderIndex - inorderStart;
node.left = BuildNode(preorder,preorderStart+1, preorderStart + inorderIndex - inorderStart, inorder, inorderStart, inorderIndex-1 );
node.right = BuildNode(preorder,preorderStart+inorderIndex-inorderStart+1,preorderEnd, inorder, inorderIndex+1,inorderEnd);
//node.left = BuildNode(preorder,preorderStart+1,preorderStart+1+offset-1,inorder,inorderStart,inorderStart+offset-1);
//node.right = BuildNode(preorder,preorderStart+1+offset,preorderEnd,inorder,inorderStart+offset+1,inorderEnd);
return node;
}
public TreeNode BuildTree(int[] preorder, int[] inorder) {
//构造字典缓存位置
for(int i=0; i<inorder.Length; i++){
dict.Add(inorder[i],i);
}
TreeNode node = BuildNode(preorder,0,preorder.Length-1, inorder,0,inorder.Length-1);
return node;
}
}