leetcode: Construct Binary Tree from Inorder and Postorder Traversal

问题描述：

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

原问题链接：https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

 

问题分析

　　在之前的问题里讨论过根据二叉树的前序和中序遍历序列构造整棵树的过程。这里的思路和前面基本一致。唯一的变化就是，因为这里是得到后序和中序的两个序列。那么我们就应该从后序的最后面开始看起。最后面的这个点是树的根节点。然后在对应的中序序列中它将数划分成了两部分。

　　这里最重要的就是要理清楚节点所在的位置关系。详细的代码实现如下：

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = buildInOrderMap(inorder);
        return buildTree(postorder.length - 1, 0, inorder.length - 1, postorder, inorder);
    }
    
    private TreeNode buildTree(int postStart, int inStart, int inEnd, int[] postorder, int[] inorder) {
        if(postStart < 0 || inStart > inEnd) return null;
        TreeNode node = new TreeNode(postorder[postStart]);
        int i = map.get(postorder[postStart]);
        node.left = buildTree(postStart - inEnd + i - 1, inStart, i - 1, postorder, inorder);
        node.right = buildTree(postStart - 1, i + 1, inEnd, postorder, inorder);
        return node;
    }
    
    private Map<Integer, Integer> buildInOrderMap(int[] inorder) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i], i);
        return map;
    }
}