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 inOrder int整型一维数组
     * @param postOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode buildTree (int[] inOrder, int[] postOrder) {

        // write code here
        if (inOrder.length == 0 || postOrder.length == 0) return null;

        return build(inOrder, postOrder, 0, inOrder.length, 0, postOrder.length);
    }

    private TreeNode build(int[] inorder, int[] postorder, int inBegin, int inEnd,
                           int poBegin, int poEnd) {
        if (poBegin == poEnd) return null;
        int rootVal = postorder[poEnd - 1];
        TreeNode root = new TreeNode(rootVal);
        if (poEnd - poBegin == 1) return root;
        int index = inBegin;
        for (; index < inEnd; ++index) {
            if (inorder[index] == rootVal) break;
        }
        // 左闭右开
        int leftInBegin = inBegin;
        int leftInEnd = index;
        int rightInBegin = index + 1;
        int rightInEnd = inEnd;
        // 左闭右开
        int leftPoBegin = poBegin;
        int leftPoEnd = poBegin + leftInEnd - leftInBegin;
        int rightPoBegin = leftPoEnd;
        int rightPoEnd = poEnd - 1;

        root.left = build(inorder, postorder, leftInBegin, leftInEnd, leftPoBegin,
                          leftPoEnd);
        root.right = build(inorder, postorder, rightInBegin, rightInEnd, rightPoBegin,
                           rightPoEnd);
        return root;
    }
}

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

该题考察的知识点是二叉树的构建和递归算法。

通过给定的中序遍历和后序遍历结果构建二叉树的功能。代码首先检查输入数组是否为空，如果是，则返回空节点。然后调用递归的 build 方法来构建二叉树。build 方法根据后序遍历数组的最后一个元素确定当前子树的根节点，并根据中序遍历数组将左右子树划分出来。然后递归地对左右子树进行构建，并连接到根节点的左右孩子上。最后返回根节点作为结果。整体思路是通过递归不断划分子问题，以构建完整的二叉树。