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

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.length == 0) {
            return null;
        } ;
        TreeNode root = new TreeNode(preOrder[0]);
        int i = find(inOrder, preOrder[0]), n = preOrder.length;
        root.left = buildTreeII(Arrays.copyOfRange(preOrder, 1, i + 1),
                                Arrays.copyOfRange(inOrder, 0, i));
        root.right = buildTreeII(Arrays.copyOfRange(preOrder, i + 1, n),
                                 Arrays.copyOfRange(inOrder, i + 1, n));
        return root;
    }

    public int find(int[] arr, int x) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == x) return i;
        }
        return -1;
    }
}

本题知识点分析：

1.二叉树前序遍历和中序遍历

2.数组遍历

3.API函数(Arrays.copyOfRange)

本题解题思路分析：

1.前序遍历第一个索引就是根节点

2.找到中序遍历中根节点的索引位置

3.利用API函数，拷贝截取数组的左边和右边，递归左子树和右子树

本题使用编程语言: Java

如果您觉得本篇文章对您有帮助的话，可以点个赞支持一下，感谢~