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

知识点

树，递归

解题思路

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

递归地建立左子树和右子树，分别使用左子树的先序遍历和中序遍历构建左子树，使用右子树的先序遍历和中序遍历构建右子树。

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

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 preOrder int整型一维数组
     * @param inOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode buildTreeII(int[] preOrder, int[] inOrder) {
        if (preOrder == null || inOrder == null || preOrder.length != inOrder.length) {
            return null;
        }

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

    private TreeNode buildTreeRecursive(int[] preOrder, int[] inOrder, int preStart,
                                        int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        // 创建根节点
        TreeNode root = new TreeNode(preOrder[preStart]);

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

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

        // 构建右子树
        root.right = buildTreeRecursive(preOrder, inOrder, preStart + leftTreeSize + 1,
                                        preEnd, rootIndex + 1, inEnd);

        return root;
    }
}