题意：根据中序和后序遍历构造二叉树
思路：
- 把中序遍历的每一个数字和对应的index放到map中
- DFS，遍历重构树
- 每次DFS，传入中序和后序的开始和结束index，
- 取后序index的末尾为跟节点
- DFS获取其左右子节点
- 返回跟节点
思想：树的先跟遍历
复杂度：时间O（n)，空间O(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 {
public TreeNode buildTree(int[] inorder, int[] postorder) {
int len = inorder.length;
if(len == 0)
return null;
HashMap<Integer, Integer> map = new HashMap();
for(int i=0;i<len;i++) {
map.put(inorder[i], i);
}
return build(inorder, postorder, 0, len-1, 0, len-1, map);
}
TreeNode build(int[] inorder, int[] postorder, int is, int ie, int ps, int pe, HashMap<Integer, Integer> map) {
if(is>ie || ps > pe || is<0||ps<0)
return null;
TreeNode cur = new TreeNode(postorder[pe]);
int index = map.get(postorder[pe]);
cur.left = build(inorder, postorder, is, index - 1, ps, ps + index - is-1, map);
cur.right = build(inorder, postorder, index+1, ie, ps+index-is, pe-1, map);
return cur;
}
}
