题解 | #重建二叉树#

注：

1.TreeNode对象用来表示树的一个节点，其函数有left、right用来表示左右结点
TreeNode构造方法为 TreeNode root = new TreeNode(pre[0]);
其中pre[0]即为节点元素值
2.数组的copyOfRange方法介绍：
Arrays.copyOfRange(int[] original, int from, int to)
1.original：第一个参数为要拷贝的数组对象
2.from：第二个参数为拷贝的开始索引位置（包含）
3.to：第三个参数为拷贝的结束索引位置（不包含）

已知前序遍历序列和中序遍历序列，重建二叉树

方法： 前序序列的第一个元素即为根节点，遍历中序序列，找到该根节点元素，根节点左边为左子树，右边为右子树，左子树和右子树在前序遍历和中序遍历中都有一个排列：
前序遍历：root 左子树前序排列 右子树前序排列
中序遍历：左子树中序排列 root 右子树中序排列
分别对左子树排列和右子树排列进行递归，最后得到完整的重建二叉树

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
           //前序pre,中序in
        if(pre.length!=0&&in.length!=0){
            TreeNode treenode=new TreeNode(pre[0]);

            int i=0;
            while(pre[0]!=in[i]){
                i++;
            }//得到中序的根节点的下标i
            //左右分割
            int[] inLeft=new int[i];
            int[] inRight=new int[in.length-i-1];
            for (int j = 0; j < inLeft.length; j++) {
                inLeft[j]=in[j];
            }
            for (int j = 0; j < inRight.length; j++) {
                inRight[j]=in[j+inLeft.length+1];
            }

            int[] preLeft=new int[i];
            int[] preRight=new int[in.length-i-1];
            for (int j = 0; j < preLeft.length; j++) {
                preLeft[j]=pre[1+j];
            }
            for (int j = 0; j < preRight.length; j++) {
                preRight[j]=pre[j+preLeft.length+1];
            }
            treenode.left=reConstructBinaryTree(preLeft,inLeft);
            treenode.right=reConstructBinaryTree(preRight,inRight);
            return treenode;
        }
        else
            return null;
    }
}

利用开头介绍的Arrays.copyOfRange(int[] original, int from, int to)方法,可以将代码简化为：

import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        // 在中序中找到前序的根
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                // 左子树，注意 copyOfRange 函数，左闭右开
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                // 右子树，注意 copyOfRange 函数，左闭右开
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;
            }
        }
        return root;
    }
}