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

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 buildTreeII (int[] preOrder, int[] inOrder) {
        // write code here
        if (preOrder.length == 0 || inOrder.length == 0) return null;
        return build(preOrder, inOrder, 0, preOrder.length, 0, inOrder.length);
    }

    private TreeNode build(int[] preOrder, int[] inOrder, int preBegin, int preEnd,
                           int inBegin, int inEnd) {
        if (preBegin == preEnd) return null;
        int rootVal = preOrder[preBegin];
        TreeNode root = new TreeNode(rootVal);
        if (preEnd - preBegin == 1) return root;
        int ind = inBegin;
        for (; ind < inEnd; ++ind) {
            if (inOrder[ind] == rootVal) break;
        }
        // 左闭右开
        int leftInBegin = inBegin;
        int leftInEnd = ind;
        int rightInBegin = leftInEnd + 1;
        int rightInEnd = inEnd;

        int leftPreBegin = preBegin + 1;
        int leftPreEnd = leftPreBegin + (leftInEnd - leftInBegin);
        int rightPreBegin = leftPreEnd;
        int rightPreEnd = preEnd;

        root.left = build(preOrder, inOrder, leftPreBegin, leftPreEnd, leftInBegin,
                          leftInEnd);
        root.right = build(preOrder, inOrder, rightPreBegin, rightPreEnd, rightInBegin,
                           rightInEnd);
        return root;
    }
}

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

该题考察的知识点是二叉树的构建和遍历算法，以及对数组的操作。

创建了一个 Solution 类，其中包含了 buildTreeII 和 build 方法。buildTreeII 方法是该类的入口方法，接收两个整数数组 preOrder 和 inOrder 作为参数，表示前序遍历和中序遍历结果。在方法内部，首先判断数组是否为空，若为空则返回 null。然后调用 build 方法进行构建二叉树，并将其作为结果返回。

build 方法是一个私有方法，接收六个参数：preOrder 和 inOrder 分别表示前序遍历和中序遍历的结果，preBegin 和 preEnd 表示前序遍历的开始索引和结束索引，inBegin 和 inEnd 表示中序遍历的开始索引和结束索引。首先判断结束索引和开始索引是否相等，如果相等，则返回 null。接着，获取前序遍历的第一个元素作为当前子树的根节点值 rootVal，并创建一个 TreeNode 对象作为当前子树的根节点。如果前序遍历的元素个数为1，则直接返回根节点。

然后，在中序遍历中找到根节点的索引，遍历中序遍历数组，当遍历到的元素与根节点值相等时，将索引保存在 ind 变量中。接下来，根据中序遍历的结果将数组分为左子树和右子树部分，确定左右子树在中序遍历和前序遍历数组中的开始索引和结束索引。

最后，递归调用 build 方法分别构建左子树和右子树，并将它们连接到当前节点的左右孩子上。最终返回根节点作为结果。

这段代码实现了通过给定的前序遍历和中序遍历结果构建二叉树的功能，并使用递归的方式进行构建。通过递归不断划分子问题，找到子树的根节点和左右子树的范围，然后再对左右子树进行递归构建。最终得到完整的二叉树。