题解 | #牛群的树形结构重建# 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 == null || postOrder == null ||
                inOrder.length != postOrder.length) {
            return null;
        }

        return buildTreeHelper(inOrder, 0, inOrder.length - 1, postOrder, 0,
                               postOrder.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 = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inOrder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        root.left = buildTreeHelper(inOrder, inStart, rootIndex - 1, postOrder,
                                    postStart, postStart + rootIndex - inStart - 1);
        root.right = buildTreeHelper(inOrder, rootIndex + 1, inEnd, postOrder,
                                     postStart + rootIndex - inStart, postEnd - 1);

        return root;
    }
}

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

这道题考察的知识点是根据中序遍历和后序遍历构建二叉树。

代码的文字解释如下：

• buildTree 方法接收两个参数，分别是中序遍历数组 inOrder 和后序遍历数组 postOrder，返回一个指向根节点的指针。
• 首先判断输入数组是否为空，以及两个数组的长度是否相等，如果不满足条件则返回空指针。
• 调用 buildTreeHelper 方法进行递归构建二叉树，初始时传入中序遍历数组的起始位置 0、结束位置 inOrder.size() - 1，以及后序遍历数组的起始位置 0、结束位置 postOrder.size() - 1。
• 在 buildTreeHelper 方法中，首先判断如果中序遍历的起始位置大于结束位置，或者后序遍历的起始位置大于结束位置，则返回空指针。
• 获取后序遍历数组的最后一个元素作为当前节点的值 rootVal。
• 创建一个新的节点 root，值为 rootVal。
• 根据中序遍历数组找到当前节点在其中的索引 rootIndex，可以通过遍历中序遍历数组来找到与 rootVal 相等的元素的索引。
• 递归构建左子树，传入中序遍历数组的起始位置 inStart、rootIndex - 1，以及后序遍历数组的起始位置 postStart、postStart + rootIndex - inStart - 1。
• 递归构建右子树，传入中序遍历数组的 rootIndex + 1、结束位置 inEnd，以及后序遍历数组的 postStart + rootIndex - inStart、postEnd - 1。
• 将构建好的左右子树连接到当前节点上。
• 返回根节点的指针。