剑指 Offer 07. 重建二叉树

题目来源：剑指 Offer 07.

题目链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

  3
 / \
9  20
  /  \
 15   7

限制：

0 <= 节点个数 <= 5000

问题分析

示例代码

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder.length ==0) return null; 
    return buildRecursion(preorder, inorder, 0, 0, preorder.length - 1);
}

public TreeNode buildRecursion(int[] preorder, int[] inorder, int index, int l, int r) {
    int rootVal = preorder[index];//根节点值
    int index2 = 0;
    for (; rootVal != inorder[index2]; index2++) ;
    TreeNode root = new TreeNode(inorder[index2]);
    TreeNode left = null, right = null;
    if (index2 > l)
        left = buildRecursion(preorder, inorder, index + 1, l, index2 - 1);
    if (index2 < r)
        right = buildRecursion(preorder, inorder, index + (index2 - l) + 1, index2 + 1, r);
    root.left = left;
    root.right = right;
    return root;
}

执行结果：