BM40 题解 | #重建二叉树#

解题心得：

1、一个要清楚什么时候停止创建TreeNode，就是pre.size() ,vin.size()都为空时；

2、一个是要注意下标的选取，容易选错导致整个算法异常，只要对着笔记本上画出来的标识来看就没有任何问题！

            root.left = reConstructBinaryTree(
                Arrays.copyOfRange(preOrder, 1, i+1), 
                Arrays.copyOfRange(vinOrder, 0, i));
            root.right = reConstructBinaryTree(
                Arrays.copyOfRange(preOrder, i+1, n),
                Arrays.copyOfRange(vinOrder, i+1, n));

解题思路：

1、判断传入的pre、vin数组长度是否为0，若是返回null

2、创建新的根节点，

3、for循环找出根节点，在中序数组的位置，截取左右子节点的pre、vin数组递归，

4、最后返回整个root节点。

import java.util.*;


public class Solution {
    /**
     *  根据前序、中序数组重构二叉树
     * @param preOrder int整型一维数组 
     * @param vinOrder int整型一维数组 
     * @return TreeNode类
     */
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // 前序和中序数组为空说明到叶子节点底了
        // 直接返回空节点填充叶子节点的叶子
        int m = preOrder.length;
        int n = vinOrder.length;
        if(m == 0 || n == 0) {
            return null;
        }
        // 创建根节点
        TreeNode root = new TreeNode(preOrder[0]);
        for(int i=0; i<n; i++) {
            // 找到左右子节点的前序、中序数组递归
            if(preOrder[0]==vinOrder[i]) {
                root.left = reConstructBinaryTree(
                    Arrays.copyOfRange(preOrder, 1, i+1), 
                    Arrays.copyOfRange(vinOrder, 0, i));
                root.right = reConstructBinaryTree(
                    Arrays.copyOfRange(preOrder, i+1, n),
                    Arrays.copyOfRange(vinOrder, i+1, n));
                break;
            }
        }
        return root;
    }
}