题目描述
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
分治递归算法
后序遍历的次序: 左-右-中
中序遍历的次序：左-中-右
可以发现，后续遍历的最后一个节点是该序列对应树或者子树的根节点root。
从中序遍历中可以找到root的坐标（无重复元素），那么中序遍历中该坐标的左边就是root中左子树的中序遍历序列，右边就是root右子树的中序遍历序列。
而在后序遍历中，可以依据中序遍历中得到的左子树序列长度切分出root左子树和右子树的后序遍历序列；
这样我们就分别得到了root的左子树的后序序列，中序序列，以及root右子树的后序序列以及中序序列
也就是切分成了子问题并且进行递归求解；
解题方法
1）使用递归，因为树或者子树的后序遍历和中序遍历序列在数组中都是连续的，所以我们可以使用边界来标记序列的长度
2）为了快速定位root在中序遍历中的位置，我们可以使用哈希表进行辅助；
3) 递归终止条件为序列的长度小于等于0，这时候返回NULL即可
复杂度
时间复杂度：O（n）
空间复杂度:O(n+log(n))
/*** 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 {Map<Integer, Integer> map;public TreeNode buildTree(int[] inorder, int[] postorder) {int n = inorder.length;map = new HashMap<> ();for (int i = 0; i < n; ++i) {map.put(inorder[i], i);}return dfs(inorder, 0, n - 1, postorder, 0 , n - 1);}private TreeNode dfs(int[] inorder, int il, int ir, int[] postorder, int pl, int pr) {if (pl > pr) {return null;}TreeNode root = new TreeNode(postorder[pr]);int mid = map.get(root.val);int leftLength = mid - il;TreeNode left = dfs(inorder, il, mid - 1, postorder, pl, pl + leftLength - 1);TreeNode right = dfs(inorder, mid + 1, ir, postorder, pl + leftLength, pr - 1);root.left = left;root.right = right;return root;}
}
