数据结构——二叉树的从前序与中序遍历序列构造二叉树

class Solution {
// 记录前序遍历的当前节点索引
    int preIndex = 0; 
    public TreeNode buildTree(int[] preorder, int[] inorder) {
  //  采用的递归的方法
        return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
    }

    public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegin, int inEnd) {
        // 区间无效（无节点），返回null这时候说明二叉树已经创建好了递归可以结束了
        if (inBegin > inEnd) {
            return null;
        }

        // 前序的当前节点作为根节点
        TreeNode root = new TreeNode(preorder[preIndex]);
        // 前序索引后移，指向下一个根节点
        preIndex++; 
        // 在中序中找到根节点的位置
        int rootIndex = findRootIndex(inorder, root.val, inBegin, inEnd);

        // 递归构建左子树（中序左区间）和右子树（中序右区间）
        root.left = buildTreeChild(preorder, inorder, inBegin, rootIndex - 1);
//        在每一个root变化的时候，子树的范围也在变化
//按着上面的图来说
/*假设前序遍历为 [1,2,3,4]，中序遍历为 [2,1,3,4]：
第一层递归：
preIndex=0，root.val = preorder[0] = 1，此时 “根节点” 是整棵树的根（值为 1）。
在中序 [2,1,3,4] 中找 1 的位置，得到 rootIndex=1，划分左子树区间 [0,0]（值 2）和右子树区间 [2,3]（值 3,4）。
第二层递归（构建左子树）：
preIndex=1（已递增），root.val = preorder[1] = 2，此时 “根节点” 是左子树的根（值为 2）。
在中序左区间 [0,0] 中找 2 的位置，得到 rootIndex=0，其左 / 右区间均无效（终止递归）。
第三层递归（构建右子树）：
preIndex=2，root.val = preorder[2] = 3，此时 “根节点” 是右子树的根（值为 3）。
在中序右区间 [2,3] 中找 3 的位置，得到 rootIndex=2，划分右子树的右区间 [3,3]（值 4）。
第四层递归（构建 3 的右子树）：
preIndex=3，root.val = preorder[3] = 4，此时 “根节点” 是 3 的右子树的根（值为 4）。
在中序区间 [3,3] 中找 4 的位置，得到 rootIndex=3，递归终止。
*/

        root.right = buildTreeChild(preorder, inorder, rootIndex + 1, inEnd);
//二叉树创建完成就是比如说root = 3,那就是3.right = 9差不多就是这样子的
        return root;
    }

    // 在中序遍历的[inBegin, inEnd]区间内找根节点的索引
    //但是其实不加inBegin,inend也可以,但是可以避免全数组遍历导致错误。
    public int findRootIndex(int[] inorder, int key, int inBegin, int inEnd) {
        for (int i = inBegin; i <= inEnd; i++) {
            if (key == inorder[i]) {
                return i;
            }
        }
        return -1; 
    }
}