105.

首先回忆一下如何根据两个顺序构造一个唯一的二叉树相信理论知识大家应该都清楚就是以

后序数组的最后一个元素为切割点先切中序数组然后根据中序数组反过来再切后序数组。

一层一层切下去每次后序数组最后一个元素就是节点元素。

如果让我们肉眼看两个序列画一棵二叉树的话应该分分钟都可以画出来。

流程如图

TreeNode{Val:postorder[pr-1]}}//

postorder[pr

递归构造左右子树拼接为当前节点的左右子树curTreeNode.Left

dfs(inorder,il,idx,postorder,pl,pl

idx

dfs(inorder,idx1,ir,postorder,pl

idx

curTreeNode难点大家应该发现了就是如何切割以及边界值找不好很容易乱套。

此时应该注意确定切割的标准是左闭右开还有左开右闭还是左闭右闭这个就是不变量要在递归中保持这个不变量。

即从最入口的时候是左闭右开则递归的过程中要一直遵循这个原则这样区间才不会乱套。

在切割的过程中会产生四个区间把握不好不变量的话一会左闭右开一会左闭右闭必然乱套

首先要切割中序数组为什么先切割中序数组呢

切割点在后序数组的最后一个元素就是用这个元素来切割中序数组的所以必须要先切割中序数组。

中序数组相对比较好切找到切割点后序数组的最后一个元素在中序数组的位置然后切割如下代码中我坚持左闭右开的原则

假设找到切割点在中序数组中的索引为idx则中序数组切割后左数组是[il,idx)即起点还是il,但是右边界是到idx,且不包含idx因为idx是当前节点的数值不可能出现在子树中的这样[il,idx)符合了我们坚持的左闭右开原则。

而中序数组的右边界则是[idx1,ir)同样排除了idx即当前递归层取出了中序数组中idx对应的数值构造了一个树节点。

curTreeNode.Left

dfs(inorder,il,idx,postorder,pl,pl

idx

dfs(inorder,idx1,ir,postorder,pl

idx

后序数组没有明确的切割元素来进行左右切割不像中序数组有明确的切割点切割点左右分开就可以了。

此时有一个很重的点就是中序数组大小一定是和后序数组的大小相同的这是必然。

中序数组我们都切成了左中序数组和右中序数组了那么后序数组就可以按照左中序数组的大小来切割切成左后序数组和右后序数组。

idx

il,左后序数组的元素个数也是右区间减去左区间的所有就是(pl

idx

后序最后一个节点一定是根节点找到根节点后可以切割中序的左右子树并切割后续的左右子树//

len(postorder)

dfs(inorder,0,len(inorder),postorder,0,len(postorder))return

root

TreeNode{Val:postorder[pr-1]}}val

postorder[pr

dfs(inorder,il,idx,postorder,pl,pl

idx

dfs(inorder,idx1,ir,postorder,pl

idx

给定两个整数数组preorder和inorder其中preorder是二叉树的先序遍历

inorder

dfs(preorder,0,len(preorder),inorder,0,len(inorder))return

root

中序的切割容易前序的切割则遵循长度和中序一致就比较容易确定了如左中序变为il,idx则长度是idx

il//

左前序的起点是pl1无疑区间长度需要是idx-il从而确定左前序右边界为pl

idx

il,inorder,il,idx)curTreeNode.Right

dfs(preorder,pl

前序和后序不能唯一确定一棵二叉树因为没有中序遍历无法确定左右部分也就是无法分割。

举一个例子