[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

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

難度：Medium

題目：105. Construct Binary Tree from Preorder and Inorder Traversal

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

Note:

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

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

思路：首先，你應該知道

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

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

是以，我們可以從

preorder

中找到整棵樹的根節點，即為

preorder[0]

，由于

preorder

和

inorder

是對同一棵樹的周遊，我們可以知道

preorder[0]

在

inorder

中一定也存在，不妨設

preorder[0]==inorder[k]

。

由于

inorder

是中序周遊，是以

k

左邊的就是根節點左子樹的中序周遊、

k

右邊的就是根節點右子樹的中序周遊。

并且，我們已經知道了根節點左子樹的節點數（與中序周遊長度相同），不妨設為

l

，我們可以知道preorder從

1

到

l+1

就是根節點左子樹的前序周遊，剩下的最後一部分就是根節點右子樹的前序周遊。

由此，我們可以計算出左子樹、右子樹的前序周遊和中序周遊，進而可以用分治的思想，将規模較大的問題分解成為兩個較小的問題，然後遞歸的進行處理，還原左子樹和右子樹，最後連通根節點一起組成一棵完整的樹。

參考代碼：

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[] preorder, int[] inorder) {
        Map<Integer, Integer> inorderMap = new HashMap<Integer, Integer>();
        for(int i=0; i<inorder.length; i++)
            inorderMap.put(inorder[i],i);
        return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1, inorderMap);
    }
    
    public TreeNode buildTree(int[] preorder, int pLeft, int pRight, int[] inorder, int iLeft, int iRight, Map<Integer,Integer> inorderMap){
        if(pLeft>pRight || iLeft>iRight)
            return null;
        TreeNode cur = new TreeNode(preorder[pLeft]);
        //int i=0;
        //for(i=iLeft; i<= iRight; i++)
        //    if(preorder[pLeft] == inorder[i])
        //        break;
        int i = inorderMap.get(preorder[pLeft]);
        
        cur.left = buildTree(preorder, pLeft+1, pLeft+i-iLeft, inorder, iLeft, i-1, inorderMap);
        cur.right = buildTree(preorder, pLeft+i-iLeft+1, pRight, inorder, i+1, iRight, inorderMap);
        return cur;
    }
}