题解 | #重建二叉树#
重建二叉树
http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
法一：三指针
- preStart，他表示的是前序遍历开始的位置；
- inStart，他表示的是中序遍历开始的位置；
- inEnd，他表示的是中序遍历结束的位置。
找到了前序遍历的结点在中序遍历的位置，我们就可以把中序遍历数组分解为两部分了
[0，index -1]就是根节点左子树的所有节点，
[index+1，inorder. length-1]就是根节点右子树的所有节点。
法二：使用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某个祖先节点的右节点
