题解 | 重建二叉树

import java.util.*;

// public class TreeNode {
//     int val = 0;
//     TreeNode left = null;
//     TreeNode right = null;
//     public TreeNode(int val) {
//         this.val = val;
//     }
// }

[1,2,4,7,3,5,6,8]
[4,7,2,1,5,3,8,6]


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型一维数组
     * @param vinOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode solve(int[] preOrder, int preLeft, int preRight, int[] vinOrder,
                          int vinLeft, int vinRight) {
        if (preLeft > preRight) {
            return null;
        }
        int headVal = preOrder[preLeft];
        TreeNode head = new TreeNode(headVal);
        int partition = -1;
        int l_preLeft, l_preRight, l_vinLeft, l_vinRight;
        int r_preLeft, r_preRight, r_vinLeft, r_vinRight;
        // 由中序排列确定划分 
        for (int i = vinLeft; i <= vinRight; ++i) {
            if (vinOrder[i] == headVal) {
                partition = i;
                break;
            }
        }
        l_vinLeft = vinLeft;
        l_vinRight = partition - 1;
        r_vinLeft = partition + 1;
        r_vinRight = vinRight;

        l_preLeft = preLeft + 1; // 左子前序起点
        l_preRight = preLeft + partition - vinLeft;
        r_preLeft = l_preRight + 1;
        r_preRight = preRight;

        head.left = solve(preOrder, l_preLeft, l_preRight, vinOrder, l_vinLeft, l_vinRight);
        head.right = solve(preOrder, r_preLeft, r_preRight, vinOrder, r_vinLeft, r_vinRight);
        return head;
    }
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // write code here
        return solve(preOrder, 0, preOrder.length - 1, vinOrder, 0, vinOrder.length - 1);

    }
}