【树】--重建二叉树

• 前序遍历顺序：根节点->左子节点->右子节点
• 中序遍历顺序：左子节点->根节点->右子节点

前序中的第一个元素能把中序分成两部分,然后对左右两部分做同样操作，必然使用递归方法,递归出口，在最后只有一个元素，递归结束

package org.example.tree;

import org.example.model.TreeNode;

import java.util.Arrays;


public class practiceTree01 {

    

    
     public TreeNode reConstructBinaryTree(int[] pre,int[] ino){

         if (pre.length==0){
             return null;
         }
         
         //前序第一个元素
         int rootVal = pre[0];

         //将中序分成左右子树两部分
         TreeNode treeNode = new TreeNode(rootVal);
         int rootIndex=0;
         for (int i = 0; i < ino.length; i++) {
             if (rootVal==ino[i]){
                 rootIndex=i;
                 break;
             }
         }

         //左子树
           //前序 copyOfRange 范围0<=X<10
         Arrays.copyOfRange(pre, 1, rootIndex + 1);
           //中序
         Arrays.copyOfRange(ino, 0, rootIndex );
         treeNode.setLeftNode(reConstructBinaryTree(Arrays.copyOfRange(pre, 1, rootIndex + 1),Arrays.copyOfRange(ino, 0, rootIndex )));

         //同理右子树
         Arrays.copyOfRange(pre, rootIndex + 1, pre.length);
         Arrays.copyOfRange(ino, rootIndex+1, ino.length );
         treeNode.setRightNode(reConstructBinaryTree(Arrays.copyOfRange(pre, rootIndex + 1, pre.length),Arrays.copyOfRange(ino, rootIndex+1, ino.length )));

         return treeNode;
     }



}