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

标签：前序遍历；中序遍历

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

思路：

//preorder：中左右 inorder 左中右
// preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
// 不从代码角度，形象划分过程如下：
//       3                       3
//   9       15 20 7       9           20
//                                 15       7
// 前序遍历中下一个节点和上一个节点关系：是其左孩子 是其右孩子  和上一个节点没关系，自己是一个独立根节点
// 如何判断关系呢？在上一个节点划分出来的左边能找到下一个节点就是左孩子...

int i=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return search(preorder,inorder,0,inorder.length);
    }
    public TreeNode search(int[] preorder, int[] inorder,int left,int right){
        if(i>=preorder.length)
            return null;
        TreeNode node=new TreeNode(preorder[i]);
        int j=left;
        boolean flag=false;
        for(j=left;j<right;j++){
            if(inorder[j]==preorder[i]){
                i++;
                flag=true;
                break;
            }
        }
        if(!flag) // 不是左|右孩子 左|右孩子设为null
            return null;
        node.left=search(preorder,inorder,left,j);// 看是否是其左孩子
        node.right=search(preorder,inorder,j+1,right); // 看是否是其右孩子
        return node; // 是独立节点
    }