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

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.length == 0) return null;
        int n = inOrder.length;
        // 后序遍历最后一个索引位置必然是根节点
        int x = postOrder[n - 1];
        TreeNode root = new TreeNode(x);
        // 如果就一个根节点，那么直接返回
        if (inOrder.length == 1) return root;
        // 找到根节点索引下标(在中序遍历中)
        int i = find(inOrder, x);
        root.left = buildTree(Arrays.copyOfRange(inOrder, 0, i),
                              Arrays.copyOfRange(postOrder, 0, i));
        root.right = buildTree(Arrays.copyOfRange(inOrder, i + 1, n),
                               Arrays.copyOfRange(postOrder, i, n - 1));
        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.递归

4.数学模拟

本题解题思路分析：

1.根据后序遍历的最后一个索引，找到根节点的值

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

3.中序遍历根节点的左边都左子树，右边都是右子树

4.利用Array.copyof进行拷贝，然后递归左子树和右子树

本题使用编程语言: Java