题解 | #牛群的树形结构重建II# java

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型一维数组
     * @param inOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null ||
                inorder.length != postorder.length) {
            return null;
        }
        return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0,
                               postorder.length - 1);
    }

    public TreeNode buildTreeII(int[] preOrder, int[] inOrder) {
        if (preOrder == null || inOrder == null || preOrder.length != inOrder.length) {
            return null;
        }
        return buildTreeHelper2(preOrder, 0, preOrder.length - 1, inOrder, 0,
                                inOrder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd,
                                     int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }

        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);

        int rootIndex = inStart;
        while (inorder[rootIndex] != rootVal) {
            rootIndex++;
        }

        int leftSize = rootIndex - inStart;

        root.left = buildTreeHelper(inorder, inStart, rootIndex - 1, postorder,
                                    postStart, postStart + leftSize - 1);
        root.right = buildTreeHelper(inorder, rootIndex + 1, inEnd, postorder,
                                     postStart + leftSize, postEnd - 1);

        return root;
    }

    private TreeNode buildTreeHelper2(int[] preorder, int preStart, int preEnd,
                                      int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        int rootIndex = inStart;
        while (inorder[rootIndex] != rootVal) {
            rootIndex++;
        }

        int leftSize = rootIndex - inStart;

        root.left = buildTreeHelper2(preorder, preStart + 1, preStart + leftSize,
                                     inorder, inStart, rootIndex - 1);
        root.right = buildTreeHelper2(preorder, preStart + leftSize + 1, preEnd,
                                      inorder, rootIndex + 1, inEnd);

        return root;
    }
}

代码使用的编程语言是Java。

该题考察根据给定的先序遍历和中序遍历数组构建二叉树。

主要的方法是 buildTreeII，它接收先序遍历数组 preOrder 和中序遍历数组 inOrder 作为参数，并返回构建好的二叉树的根节点。

代码中buildTreeHelper2用于递归地构建二叉树。该方法接收先序遍历数组、中序遍历数组以及数组的起始和结束索引作为参数，然后根据先序遍历数组的第一个节点创建根节点，并在中序遍历数组中找到根节点的位置。然后，根据根节点在中序遍历数组中的位置，可以确定左子树和右子树的范围，进而递归地构建左子树和右子树。

通过递归调用 buildTreeHelper2 方法，可以从先序遍历和中序遍历数组中构建出完整的二叉树。