从中序与后序遍历构造二叉树

来源Leetcode第106题从中序与后序遍历构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

  3
 / \
9  20
  /  \
 15   7

---

递归构造

思路同上一题，先确定根节点，然后在中序遍历中找根节点的位置，然后分出左子树和右子树。

HashMap<Integer,Integer> map = new HashMap<>();
int [] inorder,postorder;
public TreeNode buildTree(int[] inorder, int[] postorder) {
    for(int i = 0 ; i < inorder.length ; i++)
        map.put(inorder[i],i);
    this.inorder = inorder;
    this.postorder = postorder;
    return helper(0,postorder.length,0,inorder.length);
}

private TreeNode helper(int p_start,int p_end,int i_start,int i_end){
    if(p_start == p_end)
        return null;
    TreeNode root = new TreeNode(this.postorder[p_end - 1]);  //构造根节点
    int i_root_index = this.map.get(this.postorder[p_end - 1]);  //得到中序遍历根节点的位置
    int left = i_root_index - i_start;  //这一块为根节点的左子树
    root.left = helper(p_start , p_start + left,i_start,i_root_index);
    root.right = helper(p_start + left,p_end - 1,i_root_index + 1 , i_end);
    return root;
}