通过前序遍历和中序遍历后的序列还原二叉树
//输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。//假设输入的前序遍历和中序遍历的结果中都不含重复的数字。//例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。/* function TreeNode(x) {this.val = x;this.left = null;this.right = null;} */function reConstructBinaryTree(pre, vin){if(pre.length == 0 || vin.length == 0){return null;}var index = vin.indexOf(pre[0]); //获取根节点var leftTree = vin.slice(0,index),rightTree = vin.slice(index+1);var node = new TreeNode(vin[index]); //新建二叉树node.left = reConstructBinaryTree(pre.slice(1,index+1),leftTree);node.right = reConstructBinaryTree(pre.slice(index+1),rightTree);return node;}
通过前序遍历和中序遍历后的序列还原二叉树
前序遍历：1,2,4,7,3,5,6,8 根-左-右
中序遍历：4,7,2,1,5,3,8,6 左-根-右
步骤：
（1）根据前序遍历第一个节点就是原二叉树的根节点，求得根节点（1）；
（2）在中序遍历中找到根节点的位置，根节点左边即为左子树节点（4,7,2），右边即为右子树节点（5,3,6,8）；
（3）根据左子树的前序（2,4,7）和中序遍历（4,7,2），求出左子树的根节点（2）、左子树（4,7）和右子树节点（null）；
根据右子树的前序（3,5,6,8）和中序遍历（5,3,8,6），求出右子树的根节点（3）、左子树（5）和右子树节点（8,6）；
（4）依次逐层，直至没有子节点为止
最后求得原二叉树为：
1/ \* 2 3/ / \* 4 5 6\ /7 8*/