題目07：重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。
假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。

舉例說明

輸入 ：前序遍歷序列｛ 1, 2, 4, 7, 3, 5, 6, 8｝和中序遍歷序列｛4, 7, 2, 1, 5, 3, 8，6}
重建出下所示的二叉樹并輸出它的頭結(jié)點。

              1
           /     \
          2       3
         /       / \
        4       5   6
         \         /
          7       8

思路

整個的思路是：前序定根，中序分左右。

• 先序遍歷序列的第一個數(shù)字是根結(jié)點值
• 中序遍歷中根結(jié)點的左邊序列是左子樹，右邊序列是右子樹

解題是特別還需要處理不符合條件的情況：序列為空的情況；兩序列元素個數(shù)不同的情況；兩序列中元素不相同的情況。

步驟

1. 前序第一個數(shù)是根，找到根
2. 用根的value在中序遍歷找到根（同一個），記下根在中序遍歷的index
3. 遞歸調(diào)用建立左右子樹

代碼實現(xiàn)

public class _07 {
    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
        public BinaryTreeNode() {
        }
        public BinaryTreeNode(int value) {
            this.value = value;
        }
    }

    public static BinaryTreeNode construct(int[] preorder, int[] inorder) {
        //1. 兩個數(shù)組都不能為空 2. 都有數(shù)據(jù) 3. 數(shù)據(jù)的數(shù)目相同
        if (preorder == null || inorder == null || preorder.length != inorder.length || inorder.length < 1) {
            return null;
        }
        return construct(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    /**
     * @param preorder 前序遍歷
     * @param ps : PreStart      前序遍歷的開始位置
     * @param pe : PreEnd      前序遍歷的結(jié)束位置
     * @param inorder  中序遍歷
     * @param is       中序遍歷的開始位置
     * @param ie       中序遍歷的結(jié)束位置
     * @return 樹的根結(jié)點
     */
    public static BinaryTreeNode construct(int[] preorder, int ps, int pe, int[] inorder, int is, int ie) {
        if (ps > pe) {// 開始位置大于結(jié)束位置說明已經(jīng)沒有需要處理的元素了
            return null;
        }
        int value = preorder[ps];// 取前序遍歷的第一個數(shù)字，就是當前的根結(jié)點
        
        int index = is; 
        while (index <= ie && inorder[index] != value) {
            index++;// 在中序遍歷的數(shù)組中找根結(jié)點的位置
        }
        // 如果在整個中序遍歷的數(shù)組中沒有找到，說明輸入的參數(shù)是不合法的，拋出異常
        if (index > ie) {
            throw new RuntimeException("Invalid input");
        }

        //用前序遍歷得到的value的值  創(chuàng)建當前的根結(jié)點
        BinaryTreeNode node = new BinaryTreeNode(value);
        // 遞歸構(gòu)建當前根結(jié)點的左子樹，左子樹的元素個數(shù)：index-is+1個
        // 左子樹對應(yīng)的 前序遍歷的位置在[ps+1, ps+ index-is（加上左子樹長度-1）]
        // 左子樹對應(yīng)的 中序遍歷的位置在[is, index-1]
        node.left = construct(preorder, ps + 1, ps + index - is, inorder, is, index - 1);
        // 遞歸構(gòu)建當前根結(jié)點的右子樹，右子樹的元素個數(shù)：ie-index個
        // 右子樹對應(yīng)的 前序遍歷的位置在[ps+  index-is+1（加上右子樹長度-1）, pe]
        // 右子樹對應(yīng)的 中序遍歷的位置在[index+1, ie]
        node.right = construct(preorder, ps + index - is + 1, pe, inorder, index + 1, ie);  
        return node;// 返回創(chuàng)建的樹的 根結(jié)點
    }

    // for test:中序遍歷二叉樹
    public static void printTree(BinaryTreeNode root) {
        if (root != null) {
            printTree(root.left);
            System.out.print(root.value + " ");
            printTree(root.right);
        }
    }
    public static void main(String[] args) {
        // 普通二叉樹
        //              1
        //           /     \
        //          2       3
        //         /       / \
        //        4       5   6
        //         \         /
        //          7       8
        int[] preorder = { 1, 2, 4, 7, 3, 5, 6, 8 };
        int[] inorder = { 4, 7, 2, 1, 5, 3, 8, 6 };
        BinaryTreeNode root = construct(preorder, inorder);
        printTree(root);
    }
}

輸出：

4 7 2 1 5 3 8 6