二叉树还原

二叉树是什么？什么是先序遍历，等等这些问题回头开个专题文章讲述，今天主要弄得是二叉树还原。

假设我们手头有一个一个先序遍历的数列，一个中序遍历的数列，现在让我们还原对应的二叉树，怎么做？（中序和后序也一样）

因为是先序遍历的，所以对应的数列对应得第一个值就是原二叉树的根节点，我们只需要去先序遍历的第一个元素即可。

得到了根节点我们直接去中序遍历中找到根节点对应的序号（nodeIndex），用indexOf取得，这样我们可以说知道了根节点对应的左右子树中的数值。

接着，我们对得到的左右子树进行上述操作，也就是递归，并返回递归的结果，将其绑定在根节点的左右，一个二叉树还原就做好了。

这是我写出的对应的代码：

这个算法的迷惑点对我来说有两个，一个是递归得到的先序遍历，中序遍历中的参数如何得出的？二是怎么知道已经遍历完了？

对于第一个问题，我们来进行推导：

对于左子树(leftArr)

NLR中，因为这个是先序遍历，所以根节点是第一个，slice的序号应该从第二个数也就是1开始，然后截止到整个左子树的长度为止，左子树的长度是多少呢？因为有个中序遍历，他的左子树长度就是根节点的序号，也就是nodeIndex，所以slice的截止参数应该是nodeIndex+1(slice算头不算尾)

LNR中，对于中序遍历，起点就是左子树的开始，结束为止为根节点前，所以左右的参数为0，nodeIndex

对于右子树（rightArr）

NLR中，从前面的截取位置开始，到最后一直是，截取位置是nodeIndex+1,所以照抄

LNR中，根节点后的序号应该是nodeIndex+1,所以也是nodeIndex+1

第一个问题得到了解决

第二个问题：

这个很简单，我们在开头直接判断，如果传的NLR为空，直接返回，也就是判断NLR[0]是否存在即可

这就是今天的算法和总结了，每天一个，强身健脑，明天见！