二叉樹攻略之：從前序與中序周遊序列構造二叉樹

題目

給定一棵樹的前序周遊 preorder 與中序周遊 inorder。請構造二叉樹并傳回其根節點。

解題思路

根據題意, 我們知道前序周遊的形式是先周遊根節點，然後是左子樹，最後是右子樹；中序周遊的形式是，先左子樹，再根節點，最後是右節點；

隻要我們在中序周遊中定位到根節點，那麼我們就可以分别知道左子樹和右子樹中的節點數目。由于同一顆子樹的前序周遊和中序周遊的長度顯然是相同的，是以我們就可以對應到前序周遊的結果中，對上述形式中的所有左右括号進行定位。

這樣以來，我們就知道了左子樹的前序周遊和中序周遊結果，以及右子樹的前序周遊和中序周遊結果，我們就可以遞歸地對構造出左子樹和右子樹，再将這兩顆子樹接到根節點的左右位置。

在中序周遊中對根節點進行定位時，我們可以考慮使用哈希表來幫助我們快速地定位根節點。對于哈希映射中的每個鍵值對，鍵表示一個元素（節點的值），值表示其在中序周遊中的出現位置，代碼實作如下：

代碼實作

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public HashMap<Integer, Integer> map = new HashMap();
    int[] preOrder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        this.preOrder = preorder;

        return helper(0, inorder.length - 1, 0, preOrder.length - 1);
    }

    public TreeNode helper(int inStart, int inEnd, int preStart, int preEnd) {
        if (inStart > inEnd || preStart > preEnd) return null;
        int root = preOrder[preStart]; 
        int pos = map.get(root);
        TreeNode node = new TreeNode(root);
        node.left = helper(inStart, pos - 1, preStart + 1, preStart + pos - inStart);
        node.right = helper(pos + 1, inEnd, preStart + pos - inStart + 1, preEnd);
        return node;      

最後

複雜度分析：

• 時間複雜度：O(n)，其中 n 是樹中的節點個數。
• 空間複雜度：O(n)，除去傳回的答案需要的 O(n) 空間之外，我們還需要使用 O(n) 的空間存儲哈希映射，以及 O(h)（其中 h 是樹的高度）的空間表示遞歸時棧空間。這裡 h < n，是以總空間複雜度為 O(n)。

複雜度分析

時間複雜度：O(N)，其中 N 為二叉樹的節點數。每個節點會且僅會被周遊一次。

1. 閱讀完記得給我點個贊哦，有👍 有動力
2. 關注公衆号---​​HelloWorld傑少​​，第一時間推送新姿勢