法一：三指针

  • preStart，他表示的是前序遍历开始的位置；
  • inStart，他表示的是中序遍历开始的位置；
  • inEnd，他表示的是中序遍历结束的位置。 找到了前序遍历的结点在中序遍历的位置，我们就可以把中序遍历数组分解为两部分了
    [0，index -1]就是根节点左子树的所有节点，
    [index+1，inorder. length-1]就是根节点右子树的所有节点。
    alt

法二：使用Arraylist

先把数组转化为list集合，然后在list集合中进行截取，这样效率明显不是很高，实际上我们还可以不使用list，不对数组进行截取。

int mid = inorderList.indexOf(rootVal);
root.left = helper(preorderList, inorderList.subList(0, mid));
root.right = helper(preorderList, inorderList.subList(mid + 1, inorderList.size()));

法三：使用栈

  • 前序遍历挨着的两个值比如m和n;
  • 如果m的左子树不为空，那么n就是m左子树节点的值;
  • 如果一个结点没有左子树只有右子树，那么n就是m右子树节点的值;
  • 如果一个结点既没有左子树也没有右子树，那么n就是m某个祖先节点的右节点 alt alt