题解 | #重建二叉树#

题目：重建二叉树

描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

示例1：输入：[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]，返回值：{1,2,5,3,4,6,7}

解法一：

思路分析：首先我们要清楚的一点是前序遍历的第一个数字为根节点的值，在中序遍历中，根节点的值在该序列的中间，左子树的值位于根节点的左边，右子树的结点的值位于根节点的值的右边，通过扫描中序遍历，就可以找到根节点的值。因为前序遍历的遍历规则为，在根节点之后首先遍历左子树，其次遍历右子树，所以由后序遍历能够推出左子树中结点的数目，前序遍历遍历根节点之后相同数目的值都是左子树的结点的值，剩下的是右子树的值，通过构建左右子树，将剩余的部分通过递归就能够完成相应操作。

实例分析：输入：前序遍历[1,2,3,4,5,6,7],中序遍历[3,2,4,1,6,5,7]

首先根据前序遍历可以得出，root的值为1，根据中序遍历可以得出3，2，4为1的左子树，6，5，7为1的右子树。然后再次递归，运用相同的原理，判断得出最终的树为下表所示。

构建表格得出最终的二叉树为：

具体C++程序为：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vectorpre,vectorvin) {
        if(pre.size() == 0 || pre.size() != vin.size())
            return nullptr;
        int root = pre[0];//树的第一个值为pre的第一个元素
        TreeNode *node = new TreeNode(root);
        //如果只剩一个节点了，那么可以直接返回
        if (pre.size() == 1)
            return node;
        auto posi = find(vin.begin(), vin.end(), root);
        //检测如果出现错误
        if (posi == vin.end()) {
            return nullptr;
        }
        int leftSize = posi - vin.begin();
        int rightSize = vin.end() - posi - 1;
        //递归求解
        node->left = reConstructBinaryTree(vector(pre.begin() + 1, pre.begin() + 1 + leftSize),
        vector(vin.begin(), vin.begin() + leftSize));
        node->right = reConstructBinaryTree(vector(pre.begin() + 1 + leftSize, pre.end()),
        vector(vin.begin() + leftSize + 1, vin.end()));
    return node;
    }
};

遍历全部结点最终得到结果，所以时间复杂度为O(N)，时间复杂度为O(N)。

解法二（与解法一一样使用递归遍历的方法，不同在于使用copyOfRange()函数程序简洁易懂）：

思路分析：总结根据中序遍历和前序遍历确定二叉树，首先根据前序确定根节点，根据根节点在中序遍历中的位置分割出左右子序列，对其他子序列进行递归处理就可完成分解过程。在具体应用过程中，我们可以直接使用java中的Arrays.copyOfRange()函数，copyOfRange是输入java.util包中的Arrays类的静态内部方法，可以被类直接调用。该函数的主要用途是对一个已有的数组进行截取复制，复制出一个左闭右开区间的数组。copyOfRange(int []original,int from,int to),original为原始的int型数组，from为开始角标值，to为终止角标值。

import java.util.Arrays;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if (pre.length == 0 || vin.length == 0) {//特殊情况特殊讨论
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);//确定根节点
        //在中序中找到前序的根
        for (int i = 0; i < vin.length; i++) {
            if (vin[i] == pre[0]) {
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));//左子树截取
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));//右子树截取
                break;
            }
        }
        return root;
    }
}