[数据结构与算法]leetcode 105. 从前序与中序遍历序列构造二叉树数的遍历

地址 ：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

题目很简单，根据前序 和中序构树。

二叉树中，根据两种遍历构建树，其中一种必须是中序才能唯一确定。

前/中/后序遍历都是以根结点为参考，前序即先遍历根结点，再遍历左右孩子。中序为先遍历左孩子，再遍历根结点，最后右孩子。后续遍历是先遍历左右孩子，最后是根结点。

前序： [ 根结点（左孩子）（右孩子）]
中序：[ （左孩子）根结点（右孩子）]
后序：[ （左孩子）（右孩子）根结点]

构树的核心是不断递归。
一个比较复杂的点，是在于计算各个区间的起始位置。需要点耐心

参数传入的是int[]，最初的想法是将int[]转为arrayist，但没有太简易的方法，只能for循环实现。但后续需要对list进行分割，arraylist中有sublist方法，可以返回数组切片，但是返回值不是arraylist，而是一个内部类。需要用List作为类型来遍历。但时间比较长。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        ArrayList<Integer> pre =  new  ArrayList(len);//new ArrayList(preorder);
        ArrayList<Integer> order = new ArrayList(len);//new ArrayList(inorder);
        for(int i:preorder){
            pre.add(i);
        }
        for(int i:inorder){
            order.add(i);
        }   
        return building(pre.subList(0,len),order.subList(0,len),null);
    }
    private TreeNode building( List<Integer> preorder, List<Integer> inorder,TreeNode root){//SubList
    //private void building( ArrayList<Integer> preorder, ArrayList<Integer> inorder,TreeNode root){
        int len = preorder.size();
        //System.out.println("pre "+preorder);
        //System.out.println("in "+inorder);
        if( len > 0 ){
            root = new TreeNode();
            int val = preorder.get(0);
            int index = inorder.indexOf(val);
            root.val = val;
            //System.out.print(root == null);
            if(index != -1){
                if(index >0){ // left children
                //root.left = new TreeNode();
                    root.left = building(preorder.subList(1,index+1),inorder.subList(0,index),root.left );// subList
                }
                if(index <len-1){
                    //root.right = new TreeNode();
                    root .right = building(preorder.subList(index+1,len),inorder.subList(index+1,len),root.right);
                }
                
            }

        }
        return root;
    }
}
执行用时: 19 ms
内存消耗: 38.3 MB

可优化的地方再与idnexOf，可以通过map来快速查找。经典问题，涉及到查找的，都可以试试map来加速。但map中只能存全局的index，不能使用切片后的，故放弃arraylist，直接使用int[].

class Solution {
    
    HashMap<Integer,Integer> map = new HashMap();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = null;

        int len = preorder.length;

        for(int i=0;i<len;i++){
            map.put(inorder[i],i);
        }
        
        build(0,len-1,0,len-1,root,preorder,inorder);// root 为 null
        return root;

    }

    private void build(int pl,int pr,int il,int ir ,TreeNode root,int[] preorder,int[] inorder){
        if(pl <= pr){
            root = new TreeNode();
            root.val = preorder[pl];
            int index = map.get(root.val);

            int len = index -1-il;
            if(il < index){
                root.left = new TreeNode();
                build(pl+1,pl+1+len,il,index-1,root.left,preorder,inorder);
            }
            if(index <ir){
                root.right = new TreeNode();
                build(pl+2+len,pr,index+1,ir,root.right,preorder,inorder);
            }

        }
    }

}

以上的代码会返回null。java中除基本类型外，参数都是引用传递。但是，有一个例外，就是当实参为null时，其实，它依然是一个值传递。如果root=null，相当于值查undi，是不行的。

class Solution {
    
    HashMap<Integer,Integer> map = new HashMap();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root =null;

        int len = preorder.length;


        if(len >0){

        for(int i=0;i<len;i++){
            map.put(inorder[i],i);
        }
            root = new TreeNode();
            build(0,len-1,0,len-1,root,preorder,inorder);

        }
        
        return root;

    }

    private void build(int pl,int pr,int il,int ir ,TreeNode root,int[] preorder,int[] inorder){
        if(pl <= pr){
            //root = new TreeNode();
            root.val = preorder[pl];
            int index = map.get(root.val);

            int len = index -1-il;
            if(il < index){
                root.left = new TreeNode();
                build(pl+1,pl+1+len,il,index-1,root.left,preorder,inorder);
            }
            if(index <ir){
                root.right = new TreeNode();
                build(pl+2+len,pr,index+1,ir,root.right,preorder,inorder);
            }

        }
    }

}