题解 | #牛群的树形结构重建# 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
        int n = inOrder.length;
        return dfs(inOrder, postOrder, 0, n - 1, 0, n - 1);
    }

    private TreeNode dfs(int[] inOrder, int[] postOrder, int left, int right,
                         int l2, int r2) {
        if (left > right || l2 > r2) {
            return null;
        }

        int val = postOrder[r2];
        TreeNode root = new TreeNode(val);

        int len = 0;
        for (int i = left; i <= right && inOrder[i] != val; i++) {
            len++;
        }

        root.left = dfs(inOrder, postOrder, left, left + len - 1, l2, l2 + len - 1);
        root.right = dfs(inOrder, postOrder, left + len + 1, right, l2 + len, r2 - 1);

        return root;
    }
}

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

这段代码考察的知识点有：

• 递归：通过递归实现树的构建。
• 数组操作：根据中序遍历结果和后序遍历结果，确定树节点的位置。
• 树的构建：根据中序遍历和后序遍历的特点，逐步构建树的左子树和右子树。

下面是代码的文字解释大纲：

1. 构建 TreeNode 类：定义一个树节点类 TreeNode，包含一个整数类型的值 val，以及左子树 left 和右子树 right 的引用。
2. 构建 Solution 类：定义一个解决方案类 Solution，其中包含一个构建树的方法 buildTree。
3. buildTree 方法参数说明：该方法接受两个 int 数组类型的参数 inOrder 和 postOrder，分别表示中序遍历和后序遍历的结果。
4. 定义变量和递归函数：在 buildTree 方法中，首先获取中序遍历结果的长度，并定义了一个递归函数 dfs，该函数用于构建树。
5. 递归构建树：在 dfs 函数中，根据传入的左右边界和后序遍历结果的左右边界，获取当前节点的值 val。然后创建一个新的 TreeNode 对象作为根节点，并将 val 赋值给根节点的值。
6. 计算左子树和右子树长度：通过遍历中序遍历结果，计算出左子树的长度 len。如果 len 大于 0，则说明存在左子树。如果右边界减去左边界减去左子树长度大于 0，则说明存在右子树。
7. 递归构建左子树和右子树：调用递归函数 dfs 构建左子树和右子树，并将返回的结果分别赋给根节点的左子树和右子树。
8. 返回根节点：返回构建好的根节点。