題目描述（中等難度）

根據(jù)二叉樹的先序遍歷和中序遍歷還原二叉樹。

解法一 遞歸

先序遍歷的順序是根節(jié)點(diǎn)，左子樹，右子樹。中序遍歷的順序是左子樹，根節(jié)點(diǎn)，右子樹。

所以我們只需要根據(jù)先序遍歷得到根節(jié)點(diǎn)，然后在中序遍歷中找到根節(jié)點(diǎn)的位置，它的左邊就是左子樹的節(jié)點(diǎn)，右邊就是右子樹的節(jié)點(diǎn)。

生成左子樹和右子樹就可以遞歸的進(jìn)行了。

比如上圖的例子，我們來分析一下。

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
首先根據(jù) preorder 找到根節(jié)點(diǎn)是 3
    
然后根據(jù)根節(jié)點(diǎn)將 inorder 分成左子樹和右子樹
左子樹
inorder [9]

右子樹
inorder [15,20,7]

把相應(yīng)的前序遍歷的數(shù)組也加進(jìn)來
左子樹
preorder[9] 
inorder [9]

右子樹
preorder[20 15 7] 
inorder [15,20,7]

現(xiàn)在我們只需要構(gòu)造左子樹和右子樹即可，成功把大問題化成了小問題
然后重復(fù)上邊的步驟繼續(xù)劃分，直到 preorder 和 inorder 都為空，返回 null 即可

事實(shí)上，我們不需要真的把 preorder 和 inorder 切分了，只需要用分別用兩個(gè)指針指向開頭和結(jié)束位置即可。注意下邊的兩個(gè)指針指向的數(shù)組范圍是包括左邊界，不包括右邊界。

對于下邊的樹的合成。

左子樹

右子樹

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
}

private TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {
    // preorder 為空，直接返回 null
    if (p_start == p_end) {
        return null;
    }
    int root_val = preorder[p_start];
    TreeNode root = new TreeNode(root_val);
    //在中序遍歷中找到根節(jié)點(diǎn)的位置
    int i_root_index = 0;
    for (int i = i_start; i < i_end; i++) {
        if (root_val == inorder[i]) {
            i_root_index = i;
            break;
        }
    }
    int leftNum = i_root_index - i_start;
    //遞歸的構(gòu)造左子樹
    root.left = buildTreeHelper(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index);
    //遞歸的構(gòu)造右子樹
    root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end);
    return root;
}

上邊的代碼很好理解，但存在一個(gè)問題，在中序遍歷中找到根節(jié)點(diǎn)的位置每次都得遍歷中序遍歷的數(shù)組去尋找，參考這里 ，我們可以用一個(gè)HashMap把中序遍歷數(shù)組的每個(gè)元素的值和下標(biāo)存起來，這樣尋找根節(jié)點(diǎn)的位置就可以直接得到了。

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

private TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end,
                                 HashMap<Integer, Integer> map) {
    if (p_start == p_end) {
        return null;
    }
    int root_val = preorder[p_start];
    TreeNode root = new TreeNode(root_val);
    int i_root_index = map.get(root_val);
    int leftNum = i_root_index - i_start;
    root.left = buildTreeHelper(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index, map);
    root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end, map);
    return root;
}

本以為已經(jīng)完美了，在 這里 又看到了令人眼前一亮的思路，就是 StefanPochmann 大神，經(jīng)常逛 Discuss 一定會注意到他，擁有 3 萬多的贊。

他也發(fā)現(xiàn)了每次都得遍歷一次去找中序遍歷數(shù)組中的根節(jié)點(diǎn)的麻煩，但他沒有用 HashMap就解決了這個(gè)問題，下邊來說一下。

用pre變量保存當(dāng)前要構(gòu)造的樹的根節(jié)點(diǎn)，從根節(jié)點(diǎn)開始遞歸的構(gòu)造左子樹和右子樹，in變量指向當(dāng)前根節(jié)點(diǎn)可用數(shù)字的開頭，然后對于當(dāng)前pre有一個(gè)停止點(diǎn)stop，從in到stop表示要構(gòu)造的樹當(dāng)前的數(shù)字范圍。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return buildTreeHelper(preorder,  inorder, (long)Integer.MAX_VALUE + 1);
}
int pre = 0;
int in = 0;
private TreeNode buildTreeHelper(int[] preorder, int[] inorder, long stop) {
    //到達(dá)末尾返回 null
    if(pre == preorder.length){
        return null;
    }
    //到達(dá)停止點(diǎn)返回 null
    //當(dāng)前停止點(diǎn)已經(jīng)用了，in 后移
    if (inorder[in] == stop) {
        in++;
        return null;
    }
    int root_val = preorder[pre++];
    TreeNode root = new TreeNode(root_val);   
    //左子樹的停止點(diǎn)是當(dāng)前的根節(jié)點(diǎn)
    root.left = buildTreeHelper(preorder,  inorder, root_val);
    //右子樹的停止點(diǎn)是當(dāng)前樹的停止點(diǎn)
    root.right = buildTreeHelper(preorder, inorder, stop);
    return root;
}

代碼很簡潔，但如果細(xì)想起來真的很難理解了。

把他的原話也貼過來吧。

Consider the example again. Instead of finding the 1 in inorder, splitting the arrays into parts and recursing on them, just recurse on the full remaining arrays and stop when you come across the 1 in inorder. That's what my above solution does. Each recursive call gets told where to stop, and it tells its subcalls where to stop. It gives its own root value as stopper to its left subcall and its parent`s stopper as stopper to its right subcall.

本來很想講清楚這個(gè)算法，但是各種畫圖，還是太難說清楚了。這里就畫幾個(gè)過程中的圖，大家也只能按照上邊的代碼走一遍，理解一下了。

      3
    /   \
   9     7
  / \
 20  15
 
前序遍歷數(shù)組和中序遍歷數(shù)組
preorder = [ 3, 9, 20, 15, 7 ]
inorder = [ 20, 9, 15, 3, 7 ]   
p 代表 pre，i 代表 in，s 代表 stop

首先構(gòu)造根節(jié)點(diǎn)為 3 的樹，可用數(shù)字是 i 到 s
s 初始化一個(gè)樹中所有的數(shù)字都不會相等的數(shù)，所以代碼中用了一個(gè) long 來表示
3, 9, 20, 15, 7 
^  
p
20, 9, 15, 3, 7
^              ^
i              s

考慮根節(jié)點(diǎn)為 3 的左子樹，                考慮根節(jié)點(diǎn)為 3 的樹的右子樹，
stop 值是當(dāng)前根節(jié)點(diǎn)的值 3                只知道 stop 值是上次的 s
新的根節(jié)點(diǎn)是 9,可用數(shù)字是 i 到 s 
不包括 s
3, 9, 20, 15, 7                       3, 9, 20, 15, 7                
   ^                                    
   p
20, 9, 15, 3, 7                       20, 9, 15, 3, 7                     
^          ^                                         ^
i          s                                         s

遞歸出口的情況
3, 9, 20, 15, 7 
       ^  
       p
20, 9, 15, 3, 7
^    
i   
s   
此時(shí) in 和 stop 相等，表明沒有可用的數(shù)字，所以返回 null，并且表明此時(shí)到達(dá)了某個(gè)樹的根節(jié)點(diǎn)，所以 i 后移。

總之他的思想就是，不再從中序遍歷中尋找根節(jié)點(diǎn)的位置，而是直接把值傳過去，表明當(dāng)前子樹的結(jié)束點(diǎn)。不過總感覺還是沒有 get 到他的點(diǎn)，in 和 stop 變量的含義也是我賦予的，對于整個(gè)算法也只是勉強(qiáng)說通，大家有好的想法可以和我交流。

解法二 迭代 棧

參考 這里，我們可以利用一個(gè)棧，用迭代實(shí)現(xiàn)。

假設(shè)我們要還原的樹是下圖

      3
    /   \
   9     7
  / \
 20  15

首先假設(shè)我們只有先序遍歷的數(shù)組，如果還原一顆樹，會遇到什么問題。

preorder = [3, 9, 20, 15, 7 ]

首先我們把 3 作為根節(jié)點(diǎn)，然后到了 9 ，就出現(xiàn)一個(gè)問題，9 是左子樹還是右子樹呢？

所以需要再加上中序遍歷的數(shù)組來確定。

inorder = [ 20, 9, 15, 3, 7 ]

我們知道中序遍歷，首先遍歷左子樹，然后是根節(jié)點(diǎn)，最后是右子樹。這里第一個(gè)遍歷的是 20 ，說明先序遍歷的 9 一定是左子樹，利用反證法證明。

假如 9 是右子樹，根據(jù)先序遍歷 preorder = [ 3, 9, 20, 15, 7 ]，說明根節(jié)點(diǎn) 3 的左子樹是空的，

左子樹為空，那么中序遍歷就會先遍歷根節(jié)點(diǎn) 3，而此時(shí)是 20，假設(shè)不成立，說明 9 是左子樹。

接下來的 20 同理，所以可以目前構(gòu)建出來的樹如下。

      3
    /   
   9    
  / 
 20  

同時(shí)，還注意到此時(shí)先序遍歷的 20 和中序遍歷 20 相等了，說明什么呢？

說明中序遍歷的下一個(gè)數(shù) 15 不是左子樹了，如果是左子樹，那么中序遍歷的第一個(gè)數(shù)就不會是 20。

所以 15 一定是右子樹了，現(xiàn)在還有個(gè)問題，它是 20 的右子樹，還是 9 的右子樹，還是 3 的右子樹？

我們來假設(shè)幾種情況，來想一下。

1. 如果是 3 的右子樹， 20 和 9 的右子樹為空，那么中序遍歷就是20 9 3 15。

2. 如果是 9 的右子樹，20 的右子樹為空，那么中序遍歷就是20 9 15。

3. 如果是 20 的右子樹，那么中序遍歷就是20 15。

之前已經(jīng)遍歷的根節(jié)點(diǎn)是 3 9 20，把它倒過來,即20 9 3，然后和上邊的三種中序遍歷比較，會發(fā)現(xiàn) 15 就是最后一次相等的節(jié)點(diǎn)的右子樹。

第 1 種情況，中序遍歷是20 9 3 15，和20 9 3 都相等，所以 15 是3 的右子樹。

第 2 種情況，中序遍歷是20 9 15，只有20 9 相等，所以 15 是 9 的右子樹。

第 3 種情況，中序遍歷就是20 15，只有20 相等，所以 20 是 15 的右子樹。

而此時(shí)我們的中序遍歷數(shù)組是inorder = [ 20, 9 ,15, 3, 7 ]，20 匹配，9匹配，最后一次匹配是 9，所以 15 是 9的右子樹。

     3
    /   
   9    
  / \
 20  15

綜上所述，我們用一個(gè)棧保存已經(jīng)遍歷過的節(jié)點(diǎn)，遍歷前序遍歷的數(shù)組，一直作為當(dāng)前根節(jié)點(diǎn)的左子樹，直到當(dāng)前節(jié)點(diǎn)和中序遍歷的數(shù)組的節(jié)點(diǎn)相等了，那么我們正序遍歷中序遍歷的數(shù)組，倒著遍歷已經(jīng)遍歷過的根節(jié)點(diǎn)（用棧的 pop 實(shí)現(xiàn)），找到最后一次相等的位置，把它作為該節(jié)點(diǎn)的右子樹。

上邊的分析就是迭代總體的思想，代碼的話還有一些細(xì)節(jié)注意一下。用一個(gè)棧保存已經(jīng)遍歷的節(jié)點(diǎn)，用 curRoot 保存當(dāng)前正在遍歷的節(jié)點(diǎn)。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) {
        return null;
    }
    Stack<TreeNode> roots = new Stack<TreeNode>();
    int pre = 0;
    int in = 0;
    //先序遍歷第一個(gè)值作為根節(jié)點(diǎn)
    TreeNode curRoot = new TreeNode(preorder[pre]);
    TreeNode root = curRoot;
    roots.push(curRoot);
    pre++;
    //遍歷前序遍歷的數(shù)組
    while (pre < preorder.length) {
        //出現(xiàn)了當(dāng)前節(jié)點(diǎn)的值和中序遍歷數(shù)組的值相等，尋找是誰的右子樹
        if (curRoot.val == inorder[in]) {
            //每次進(jìn)行出棧，實(shí)現(xiàn)倒著遍歷
            while (!roots.isEmpty() && roots.peek().val == inorder[in]) {
                curRoot = roots.peek();
                roots.pop();
                in++;
            }
            //設(shè)為當(dāng)前的右孩子
            curRoot.right = new TreeNode(preorder[pre]);
            //更新 curRoot
            curRoot = curRoot.right;
            roots.push(curRoot);
            pre++;
        } else {
            //否則的話就一直作為左子樹
            curRoot.left = new TreeNode(preorder[pre]);
            curRoot = curRoot.left;
            roots.push(curRoot);
            pre++;
        }
    }
    return root;
}

總

用常規(guī)的遞歸和 HashMap 做的話這道題是不難的，用 stop 變量省去 HashMap 的思想以及解法二的迭代可以了解一下吧，不是很容易想到。

更多詳細(xì)通俗題解詳見 leetcode.wang 。