LeetCode每日一题：剑指 Offer 07. 重建二叉树

题目分析：

• 前序遍历特点： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序，以题目示例为例：[ 3 | 9 | 20 15 7 ]
• 中序遍历特点： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序，以题目示例为例：[ 9 | 3 | 15 20 7 ]
  根据题目描述输入的前序遍历和中序遍历的结果中都不含重复的数字，其表明树中每个节点值都是唯一的。

递归解析：

• 递归参数：前序和后续遍历的数组int[] preorder,int[] inorder；左右指针int left,int right；根结点TreeNode head

• 代码实现：

  class Solution {
int rootIndex = 0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder.length == 0){
        return null;
    }
    TreeNode head = new TreeNode(0);
    return build(preorder,inorder,0,inorder.length-1,head);
}

public TreeNode build(int[] preorder,int[] inorder,int left,int right,TreeNode head){
    
    head = new TreeNode(preorder[rootIndex]);
    int i = findValue(preorder[rootIndex],inorder);
    rootIndex++;
    if(i > left && rootIndex < preorder.length){
        head.left =  build(preorder,inorder,left,i-1,head.left);
    }
    if(i < right && rootIndex < preorder.length){
        head.right = build(preorder,inorder,i+1,right,head.right);
    }
    return head;
}

public int findValue(int value,int[] target){
    for(int i = 0;i < target.length;i++){
        if(value == target[i]){
            return i;
        }
    }
    return -1;
}
}