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

知识点

树，递归

解题思路

这个问题可以使用递归来解决。我们可以根据中序遍历和后序遍历的特点来重建二叉树。

在后序遍历中，最后一个元素是根节点。然后，在中序遍历中，根节点的位置将数组分成了左子树和右子树两部分。

我们可以从后序遍历中取出根节点，然后在中序遍历中找到根节点的位置。根节点左边的元素构成了左子树的中序遍历，根节点右边的元素构成了右子树的中序遍历。

然后，我们可以递归地建立左子树和右子树，分别使用左子树的中序遍历和后序遍历构建左子树，使用右子树的中序遍历和后序遍历构建右子树。

最后，我们将根节点连接到左子树和右子树上，构建整棵树。

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) {
        if (inOrder == null || postOrder == null ||
                inOrder.length != postOrder.length) {
            return null;
        }

        // 构建二叉树
        return buildTreeRecursive(inOrder, postOrder, 0, inOrder.length - 1, 0,
                                  postOrder.length - 1);
    }

    private TreeNode buildTreeRecursive(int[] inOrder, int[] postOrder, int inStart,
                                        int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }

        // 创建根节点
        TreeNode root = new TreeNode(postOrder[postEnd]);

        // 在中序遍历中找到根节点的位置
        int rootIndex = inStart;
        while (rootIndex <= inEnd && inOrder[rootIndex] != root.val) {
            rootIndex++;
        }

        // 构建左子树
        int leftTreeSize = rootIndex - inStart;
        root.left = buildTreeRecursive(inOrder, postOrder, inStart, rootIndex - 1,
                                       postStart, postStart + leftTreeSize - 1);

        // 构建右子树
        root.right = buildTreeRecursive(inOrder, postOrder, rootIndex + 1, inEnd,
                                        postStart + leftTreeSize, postEnd - 1);

        return root;
    }
}