題目描述

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

/**
 * Created by ZengXihong 2019-05-29.
 */

import java.util.Arrays;

/**
 * # 題目描述
 * >輸入某二叉樹的前序遍歷和中序遍歷的結果，
 * 請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數(shù)字。
 * 例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，
 * 則重建二叉樹并返回。
 */

public class Solution4 {
    public  TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        //如果中序遍歷為空，則該樹不存在
        if (in.length == 0) {
            return null;
        }
        //樹的根節(jié)點為前序遍歷的第一個值，創(chuàng)建一個二叉樹
        TreeNode root = new TreeNode(pre[0]);
        // 根節(jié)點的值
        int mid = pre[0];
        //用作計算根節(jié)點在中序遍歷的對應位置，初始化為 0
        int index = 0;
        //遍歷中序遍歷，直至找到在中序遍歷中對應的位置
        for (int i = 0, len = in.length; i < len; i++) {
            if (mid == in[i]) {
                index = i;
                break;
            }
        }
        /**
         * 使用遞歸，已知 root 為根節(jié)點，求出 root 的左樹和右樹，即可返回
         * 已知 root 的值在中序遍歷的位置為 index，則表明 root 左樹的長度為 index
         * 則在 root.left  的參數(shù) pre = 原pre 的 第 1 個值 到 index+1，in = 原 in 的 第 0 個值 到 index
         * 則在 root.right 的參數(shù) pre = 原pre 的 第 index+1  個值 到 最后 ，in = 原 in 的 第 index+1 個值 到 最后
         * 注： Arrays.copyOfRange 的范圍 是  " [ ) "
         */
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, index + 1), Arrays.copyOfRange(in, 0, index));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, index + 1, pre.length), Arrays.copyOfRange(in, index + 1, in.length));
        return root;
    }
}

// Definition for binary tree
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}