二元樹的重建問題

作者：Grey

原文地址：

部落格園：二元樹的重建問題

CSDN：二元樹的重建問題

說明

二元樹的各種遍歷見二元樹的先，中，後序遍歷(遞迴，非遞迴，Morris方法)

根據中序遍歷和後序遍歷重建二元樹

連結地址：LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

特別注意，本題的約束條件中，一定要保證inorder 和 postorder 都由不同的值組成。由於

中序遍歷的順序是：左 -> 中 -> 右

後序遍歷的順序是：左 -> 右 -> 中

所以對一棵樹，其中序遍歷的樣子如下

後序遍歷的樣子如下

定義遞迴函數

TreeNode f(中序遍歷結果, int L1, int R1, 後序遍歷結果, int L2, int R2)

遞迴含義表示：中序遍歷的L1...R1和後序遍歷L2...R2構造出的二元樹，返回根節點。

所以主函數呼叫

f(inorder, 0, L, postorder, 0, L);

即為答案。

接下來實現這個遞迴函數，由於後序遍歷的最後一個節點就是樹的根節點，所以

// 樹的根節點
樹的根節點 = new TreeNode(後序遍歷最後一個節點);

樹的根節點在中序遍歷的節點位置假設在如下 index 位置

那麼在中序遍歷中，左樹為[L1......index - 1]。

中序遍歷的剩下部分用來構造右樹：[index + 1, R1],

在後序遍歷中，左樹為[L2......L2 + index - L1 - 1]

後序遍歷的剩下部分用來構造右樹：[L2 + index - L1, R2 - 1]

由於要記錄某個節點在中序遍歷中的位置，所以需要準備一個雜湊表，用於存某個元素在中序遍歷的位置。

        int L = inorder.length - 1;
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i <= L; i++) {
            m.put(inorder[i], i);
        }

完整程式碼如下

class Solution {
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (null == postorder || inorder == null || postorder.length != inorder.length) {
            return null;
        }
        int L = inorder.length - 1;
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i <= L; i++) {
            m.put(inorder[i], i);
        }
        return f(inorder, 0, L, postorder, 0, L, m);
    }

    private static TreeNode f(int[] inorder, int L1, int R1, int[] postorder, int L2, int R2, Map<Integer, Integer> m) {
        // 這種
        if (L2 > R2) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[R2]);
        // 如果只有一個節點，則直接返回
        if (L2 == R2) {
            return root;
        }
        int index = m.get(postorder[R2]);
        root.left = f(inorder, L1, index - 1, postorder, L2, L2 + index - L1 - 1, m);
        root.right = f(inorder, index + 1, R1, postorder, L2 + index - L1, R2 - 1, m);
        return root;
    }
}

根據先序遍歷和中序遍歷重建二元樹

連結地址：LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

對於一棵樹，中序遍歷的樣子如下

先序遍歷的樣子如下

而且，先序遍歷的第一個節點，就是根節點，然後定位根節點在中序遍歷的位置，假設在 index 位置，則

中序遍歷中，左樹為[L2.......index - 1]，剩餘部分[index + 1.......R2]去構造右樹。

先序遍歷中，左樹為[L1 + 1......index - L2 + L1]，剩餘部分[index - L2 + L1 + 1......R1]去構造右樹。

完整程式碼如下

class Solution {
     public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (null == preorder || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        int L = inorder.length - 1;
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i <= L; i++) {
            m.put(inorder[i], i);
        }
        return f(preorder, 0, L, inorder, 0, L, m);
    }

    private static TreeNode f(int[] preorder, int L1, int R1, int[] inorder, int L2, int R2, Map<Integer, Integer> m) {
        if (L1 > R1) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[L1]);
        if (L1 == R1) {
            return root;
        }
        int index = m.get(preorder[L1]);
        root.left = f(preorder, L1 + 1, index - L2 + L1, inorder, L2, index - 1, m);
        root.right = f(preorder, index - L2 + L1 + 1, R1, inorder, index + 1, R2, m);
        return root;
    }
}

更多

演演算法和資料結構筆記