从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树

1.想法

前序访问:根肯定都是靠前的.中序访问:先左子树,后右子树,所以先拿到根在中序遍历的位置然后根以前的都是左子树的,根以后的都是右子树的

image.png

那么怎么找到中序便利的根呢?
先和前序遍历的数组进行比较,标出每个数字在前序遍历中的序号.然后处理从0-inOrder.length的数组,找出根,分成左右两个部分.左右两个部分递归的去执行相同的过程.直到所处理的数组个数为1,或者没有返回.

_总结
1.给中序遍历每个数字标出其在前序遍历的位置
2.找出现在处理数组的根
3.数组根左边的为左子树,右边为右子树,递归处理直至数组长度为0或者为1

2.代码

class Solution {
   public TreeNode buildTree(int[] preorder, int[] inorder) {
       if(preorder.length == 0)return null;
        int[] indexOfInOrder = new int[preorder.length];
        boolean[] flagOfInOrder = new boolean[preorder.length]; //标记当前数字是否被使用,防止数字重复导致的问题
        //给中序遍历标号过程
        for(int i=0;i<inorder.length;i++){
            for(int j=0;j<preorder.length;j++){
                if(inorder[i] == preorder[j] && !flagOfInOrder[j]){
                    indexOfInOrder[i] = j;    //在中序第i个位置的数字位于前序遍历的j位置
                    flagOfInOrder[j] = true;
                    break;
                }
            }
        }
        TreeNode node = getMyNode(0,preorder.length-1,inorder,indexOfInOrder);
        return node;
    }

    private TreeNode getMyNode(int start, int end, int[] inorder,int[] indexOfInOrder) {
        if(start>end){  //数组长度为0,直接返回null
            return null;
        }
        if(start == end){ //只剩一个数字返回当前数字的节点
            return new TreeNode(inorder[start]);
        }else{
            int rootIndex = 0;
            int temp = Integer.MAX_VALUE;
            //寻找根的过程
            for(int index = start;index<=end;index++){   
                if(indexOfInOrder[index]<temp){
                    rootIndex = index;
                    temp = indexOfInOrder[index];
                }
            }
            //找到根,左边为左子树,右边为右子树
            TreeNode root = new TreeNode(inorder[rootIndex]);
            root.left = getMyNode(start,rootIndex-1,inorder,indexOfInOrder);
            root.right = getMyNode(rootIndex+1,end,inorder,indexOfInOrder);
            return root;
        }
    }
}