AlgoPressAppearance
0106-从中序与后序遍历序列构造二叉树
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1: 
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
提示:
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历
思路
中序遍历： 左根右 后续遍历： 左右根
后续遍历的最后一个数字就是 root 节点，用其从中序节点中找到位置，再从后续遍历中找到界限。 然后递归遍历构造出树的节点。 因为每个节点的数值都不相同，因此可以使用哈希表加速寻找索引
参考代码
csharp
public class Solution {
private Dictionary<int,int> inorderDict = new Dictionary<int,int>();
private TreeNode BuildNode(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){
if(inorderStart > inorderEnd){
return null;
}
//找出根节点
int rootValue = postorder[postorderEnd];
//找出中序索引
int inorderIndex = inorderDict[rootValue];
TreeNode node = new TreeNode(rootValue);
//构造左节点
node.left = BuildNode(inorder,inorderStart,inorderIndex-1,postorder,postorderStart,postorderStart + inorderIndex - inorderStart -1);
//构造右节点
node.right = BuildNode(inorder,inorderIndex+1,inorderEnd,postorder,postorderStart+inorderIndex - inorderStart,postorderEnd-1);
return node;
}
public TreeNode BuildTree(int[] inorder, int[] postorder) {
for(int i=0; i<inorder.Length;i++){
inorderDict.Add(inorder[i],i);
}
return BuildNode(inorder,0,inorder.Length-1,postorder,0,postorder.Length-1);
}
}