重建二叉树


  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，不必数组，用数组就超时了。