题解 | 重建二叉树

import java.util.*;
public class Solution {

    // 根据前序遍历和中序遍历来重建二叉树
    // 前序序列可以找到每一个树（子树）的根节点，中序遍历可以根据根节点的位置分出左右子树的所有节点
    // 通过递归，可以完整重建二叉树

    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // 注意这里的递归出口条件，整个过程中preorder和vinorder的长度都是一样的，当长度为0时就代表树已经被重建好了
        if(preOrder.length == 0 ) return null;
        
        TreeNode root = new TreeNode(preOrder[0]);
        

        for (int i = 0; i < vinOrder.length; i++) {
            if (vinOrder[i] == preOrder[0]) {
                root.left = reConstructBinaryTree(Arrays.copyOfRange(preOrder, 1, i + 1),
                                                  Arrays.copyOfRange(vinOrder, 0, i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(preOrder, i + 1,
                                                   preOrder.length), Arrays.copyOfRange(vinOrder, i + 1, vinOrder.length));
                break;
            }
        }
        return root;
    }
}