[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

連結： https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

難度：Medium

題目：106. 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.

翻譯：給定樹的中序周遊和後序周遊，構造二叉樹。 注意：樹中不存在重複項。

思路：本題與

105. Construct Binary Tree from Preorder and Inorder Traversal

類似。你要先知道

中序周遊：左子樹，根節點，右子樹

後序周遊：左子樹，右子樹，根節點

以如下這棵樹為例：

1
    --------|-------
    2               3
----|----       ----|----
4       5       6       7
           

前序周遊 1245367

中序周遊 4251637

後續周遊 4526731

我們可以發現，對于後序周遊來說，最後一個元素一定是根節點，也就是1。然後我們在中序周遊的結果裡面找到1所在的位置，那麼它的左半部分就是其左子樹，右半部分就是其右子樹。

我們将中序周遊左半部分425取出，同時發現後序周遊的結果也在相應的位置上面，隻是順序稍微不一樣，也就是452。我們可以發現，後序周遊中的2就是該子樹的根節點。

上面說到了左子樹，對于右子樹，我們取出637，同時發現後序周遊中對應的資料偏移了一格，并且順序也不一樣，為673。而3就是這顆右子樹的根節點。

重複上述過程，通過後續周遊找到根節點，然後在中序周遊資料中根據根節點拆分成兩個部分，同時将對應的後序周遊的資料也拆分成兩個部分，重複遞歸，就可以得到整個二叉樹了。

參考代碼：

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> inorderMap = new HashMap<Integer, Integer>();
        for(int i=0; i<inorder.length; i++)
            inorderMap.put(inorder[i],i);
        return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1, inorderMap);
        
    }
    
    public TreeNode buildTree(int[] inorder, int iLeft, int iRight, int[] postorder, int pLeft, int pRight, Map<Integer, Integer> inorderMap){
        if(iLeft>iRight || pLeft>pRight)
            return null;
        TreeNode cur = new TreeNode(postorder[pRight]);
        //int i = 0;
        //for(i=iLeft; i<=iRight; i++)
        //   if(postorder[pRight]==inorder[i])
        //        break;
        int i = inorderMap.get(postorder[pRight]);
        cur.left = buildTree(inorder, iLeft, i-1, postorder, pLeft, pLeft+i-iLeft-1, inorderMap);
        cur.right = buildTree(inorder, i+1, iRight, postorder, pLeft+i-iLeft, pRight-1, inorderMap);
        return cur;
    }
}