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

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) {
        // 节点为空，直接返回null
        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

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