07. 重建二叉树
补充常识：
1、须要定义二叉树类
public class TreeNode { int val; TreeNode left;//左节点 TreeNode right;//右节点 TreeNode(int x) { val = x; }}2、二叉树的遍历形式
简略来说
前序遍历：根左右:A, B, D, E, C, F, G
中序遍历：左根右:D, B, E, A, F, C, G
后序遍历：左右根:D, E, B, F, G, C, A
层序遍历：按层从左到右拜访:
[ [A], [B,C], [D,E,F,G]]二叉树的遍历（前序遍历、中序遍历、后序遍历、层序遍历）
“遇到二叉树，根本是递归”
思维：
首先前序失去根，就能从中序中分出左子树和右子树。分出的左子树，再从前序失去它的根，就能从中序中分出它的左子树和右子树，分出的右子树，再从前序失去它的根，就能从中序中分出它的左子树和右子树....
总结下来就是，前序失去根，中序分左右子树。
再明确一下左右子的在中序的范畴，用left right来示意；
以及根在前序的地位 root，和根在中序的地位 i。
假如一个二叉树,
已知此序的root,left,right,inorder_root,length=(0,0,8,5,9)
前序：987216543
中序：271869453
用前序的根[9]分：
前序：[9],87216543
中序：[27186],[9],[453]
分得前序：[9],[87216],[543]
失去
左子树1：前序：87216
左子树1：中序：27186该序的root,left,right,inorder_root=(1,0,4,3)(root+1,left,i-1,i)右子树1：前序：543
右子树1：中序：453该序的root,left,right,inorder_root=(6,6,8,7)(root+(i-left)+1,i+1,right,i)
前面以此类推
- 用左子树1的前序的根[8]分：
左子树1：前序：[8],7216
左子树1：中序：[271],[8],[6]
失去
左子树2：前序：721
左子树2：中序：271 - 用左子树2的前序的根[7]分：
左子树2：前序：[7],21
左子树2：中序：[2],[7],[1]
以此类推右子树。
但始终都以最开始的序列为参考写索引地位。
操作：
- 留神：
1、把中序装入HashMap，且数字是键值（不能反复）,索引是内容。
2、判断left>right就是null，
3、HashMap失去键值的办法get(val)
一个优化思路：用HashMap，不必数组，用数组就超时了。