题解 | #重建二叉树#

描述

给定某二叉树的前序遍历和中序遍历，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:
1.0 <= pre.length <= 2000
2.vin.length == pre.length
3.-10000 <= pre[i], vin[i] <= 10000
4.pre 和 vin 均无重复元素
5.vin出现的元素均出现在 pre里
6.只需要返回根结点，系统会自动输出整颗树做答案对比

思路

本题使用递归的思想：根节点的值很容易确定，就是pre序列的第一个元素，如何找到左子树呢？在vin序列中找到元素值和pre序列一致的元素数组下标index，那么在vin序列中index之前的元素都是左子树的结点，index之后的元素都是右子树的结点。对于左子树和右子树的根节点来说也是同样的分析思路，故可以重新定义一个方法getTreeNode()方法，递归调用。

注释的部分是自己的思考，想的有点多，不如答案这么简洁。

代码

/**
 * 二叉树的结构定义
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        return getTreeNode(0,0,vin.length-1,pre,vin);
    }

    //递归的思想：只不过我的思考存在漏洞
    public TreeNode getTreeNode(int preStart, int inStart, int inEnd, int[] pre,int[] vin){
        if (preStart > pre.length - 1 || inStart > inEnd) {
            return null;
        }

        TreeNode tree = new TreeNode(pre[preStart]);

        int index = 0;
        //确定中序遍历序列中根节点
        /*for(int i=inStart;i<vin.length;i++){
            if(vin[i] == pre[0]){
                index = i;
                break;
            }
        }*/
        //找到当前节点root在中序遍历中的位置，然后再把数组分两半
        for (int i = inStart; i <= inEnd; i++) { 
            if (vin[i] == tree.val) { 
                index = i;
                break;
            }
        }
        tree.left = getTreeNode(preStart + 1, inStart, index - 1, pre, vin);
        tree.right = getTreeNode(preStart + index - inStart + 1, index + 1, inEnd, pre, vin); 

        /*int[] leftPre = new int[index];
        int index1 = pre.length-1-index;
        int[] rightPre = new int[index1];

        if(index == 0){
            //说明没有左子树
            tree.left = null;
        }else{
            //说明有左子树

            for(int i=0;i<index;i++){
                leftPre[i]=pre[i+1];
            }
            pre = new int[index];
            for(int i=0;i<index;i++){
                pre[i]=leftPre[i];
            }
            TreeNode leftTree = new TreeNode(leftPre[0]);
            tree.left = leftTree;
        }

        if(index == pre.length-1){
            //说明没有右子树
            tree.right = null;
        }else{
            //说明右子树
            for(int j=0;j<index1;j++){
                rightPre[j]=pre[j+index+1];
            }
            vin = new int[index1];
            for(int j=0;j<index1;j++){
                vin[j]=rightPre[j];
            }
            TreeNode rightTree = new TreeNode(rightPre[0]);
            tree.right = rightTree;
        }*/
        return tree;
    }
}