105.从前序与中序遍历序列构成二叉树
感觉这道题是我目前碰到的最难的一道二叉树的题了。。。
给我们一个前序数组，一个中序数组，因为前序遍历是按照根左右的顺序来遍历树的，所以前序数组的第一个元素一定是该树的根节点，然后我们可以在中序数组中找到该数，在该数左边的一定都是树的左子树，右边的一定是右子树，因为中序数组的遍历顺序是左根右。接下来从前序数组中移除该数，然后截取slice为1:i+1，i就是中序数组中对应数的下标，也就说明了在前序数组中有多少个左子节点在根节点的左边。我最开始没想明白为什么是preorder[1:i+1]而不是preorder[1:i],后面想明白了，因为i是数组下标，所以本来就要少1，又因为slice是左闭右开的，所以这个时候就少2了，也就是说这里是排在根元素前面的元素个数，因为slice截取从1开始，你要保证后面的i个元素都是左子树，那么最后一个的下标因为是i+1，这个时候i+1-1就是后面的元素个数了，这里弄清楚了好办了，代码如下：