前中序构建二叉树

alt

  1. 根据前序遍历找到根节点
  2. 在中序遍历中找到根节点的位置
  3. 分割出左子树与右子树的元素
  4. 在前序数组中分割出左子树元素 中序数组中分割出左子树元素 构造左子树
  5. 在前序数组中分割出右子树元素 中序数组中分割出右子树元素 构造右子树
import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if (pre.length==0 || vin.length==0){
            return null;  //出口将数组截取完成长度为0
        }
      TreeNode  root=new TreeNode(pre[0]); //找到根节点
        int rootIndex=0;  
        for(int i=0;i<vin.length;i++){
            if(root.val==vin[i]){
                rootIndex=i; //找到根节点在中序遍历中的位置
                break;
            }
        }
        //构造左子树 就是切割出 左子树在前序数组中的元素 ，左子树子树在中序数组的元素。
        root.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,rootIndex+1),Arrays.copyOfRange(vin, 0,rootIndex));
         //构造右子树 就是切割出 右子树在前序数组中的元素 ，右子树子树在中序遍历的元素。
        root.right=reConstructBinaryTree(Arrays.copyOfRange(pre,rootIndex+1,pre.length),Arrays.copyOfRange(vin,rootIndex+1,vin.length));
        return root;
    }
}