关于java:offer-07-重建二叉树

重建二叉树

1. 首先前序的第一个值就是总的根节点 preorder[root]，而后再中序中找到对应的雷同的值，就找到中序中根节点的索引，定义为 inorder[i]，以此划分第一个左右子树
2. 上背后序根节点索引 preorder[root]=0；再中序中根节点索引 inorder[i]=1；依据中序根节点索引能够晓得左子树长度为 1 =inorder[i]-left（中序根节点右边都是左子树），所以左子树的根节点索引为 root+1 = 1；所以第一个左子树中序遍历的索引的左侧边界 left = 0，索引的右侧边界为 i -1=0，即本题左子树只有一个节点
3. 找到中序的根节点，那就找右子树的根节点为左子树节点个数 +1+ 1 即 inorder[i]-left+root+1（inorder[i]-left 为左子树的节点个数，inorder[i]-left+root 为中序根节点的索引号，再加 1 就是右子树的根节点地位），中序遍历右子树的左边界就是中序根节点地位 + 1 即 i +1; 中序遍历右子树右边界就是总树的长度 -1

4. 举例：
   

   题解

   用 HashMap 索引中序根节点更不便
   
   1、把中序装入 HashMap，且数字是键值（不能反复）, 索引是内容。
   2、判断 left>right 就是 null，
   3、HashMap 失去键值的办法 get(val)
   一个优化思路：用 HashMap，不必数组，用数组就超时了。