题解 | #重建二叉树#

package com.hhdd.数据结构.树;

/**
 * @Author huanghedidi
 * @Date 2022/8/23 22:44
 */
public class 重建二叉树 {
    /**
     * 根据前序遍历和中序遍历重建一棵二叉树
     *
     * @param pre
     * @param vin
     * @return
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        if (pre.length == 0 || vin.length == 0){
            return null;
        }
        return rebuild(pre, 0, pre.length - 1, vin, 0, vin.length - 1);
    }

    public TreeNode rebuild(int[] pre, int preStart, int preEnd, int[] vin, int vinStart, int vinEnd) {
        TreeNode root = new TreeNode(pre[preStart]);
        // 在中序遍历中可以找到前序遍历的节点，节点位置往前是左子树，节点位置往后是右子树
        int midIndex = vinStart;
        for (int i = vinStart; i <= vinEnd; i++) {
            if (vin[i] == pre[preStart]) {
                midIndex = i;
            }
        }
        int leftLength = midIndex - vinStart;
        int rightLength = vinEnd - midIndex;
        // 判断是否有左右子树
        if (leftLength > 0) {
            root.left = rebuild(pre, preStart + 1, preStart + leftLength, vin, vinStart, midIndex - 1);
        }
        if (rightLength > 0) {
            root.right = rebuild(pre, preStart + leftLength + 1, preEnd, vin, midIndex + 1, vinEnd);
        }
        return root;
    }
}