本文同步发表于 我的博客
本文论述了如何从二叉树的前中后遍历中的任意两种遍历后果来复原原始二叉树。本文浏览须要读者具备肯定的二叉树的遍历的算法根底。对于本文所述场景下的二叉树复原可分为两种子场景：
1. 一种可疾速定位左右子树切分点的场景；
1. 一种须要额定找到左右子树的切分点的场景；
在具体论述复原思考门路前，首先简要回顾树的遍历：
对于前序遍历，总有先遍历根节点，后遍历左子节点，后遍历右子节点；对于中序遍历，总有先遍历左子节点，后遍历根节点，后遍历右子节点；对于后序遍历，总有先遍历左子节点，后遍历右子节点，后遍历根节点。
那么，反推在前序遍历的后果中，首项肯定是根节点，即后果数组中左右子树的切分点；在后序遍历的后果，尾项肯定是根节点，即后果数组中左右子树的切分点。
本文所指 DFS 均特前中后序遍历，且二叉树中不含雷同值的节点。
如给定一个二叉树的层序遍历为 [1,2,3,4,5,6,7]，那么其前序遍历后果为 [1,2,4,5,3,6,7]，中序遍历后果为 [4,2,5,1,6,3,7]，后序遍历后果为 [4,5,2,6,7,3,1]。
从前中序遍历中复原二叉树
leetcode medium 105
const preorder = [root, ...left0, ...right0]
联合前文剖析，在前中序遍历的复原中，首先可确定前序遍历后果的首项为根节点，此时前序遍历除首项后残余的子数组为左右子树的结合体子数组。
const preorder = [root, ...left0AndRight0]
此时中序遍历的后果还没有应用，那么中序遍历的后果数组能够为咱们额定带来前序数组无奈带来的信息？
const inorder = [...left1, root, ...right1]
由上构造可知，当咱们失去树的根节点后，咱们能够据此失去左右子树所在的子数组的切分点。即能够失去左右子树的遍历后果。在失去左右子树所在的子数组后，咱们再次回到前序遍历的后果中。因为存在以下构造：
const preorder = [root, ...left0, ...right0]
且因为不论是二叉树的何种遍历，左右子树的后果数组的 程序不统一 ，但 长度肯定统一。那么咱们能够依据由中序遍历失去的左右子树所在子数组的长度失去左右子树在前序遍历中的子数组。进而最终在前序数组中失去与中序遍历的左右子树不同程序的在前序遍历后果中的左右子树。在进一步递归别离构建左右子树，最终失去实现的二叉树。
最终，失去以下实现代码：
func buildTree(preorder, inorder *[]int) *TreeNode {if len(preorder) < 1 || len(inorder) < 1 {return nil}
val := preorder[0]
var i int
for ;i < len(inorder); i++ {if inorder[i] == val {break}
}
return &TreeNode{
Val: val,
Left: buildTree(preorder[1:i+1], inorder[:i]),
Right: buildTree(preorder[i+1:], inorder[i+1:]),
}
}
此递归解法因为须要进行 N 个树节点的结构操作，那么工夫复杂度的 worse case 为 O(N)；另外须要额定 N 个空间存储新建的树节点，所以空间复杂度的 worse case 为 O(N)。
从中后序遍历中复原二叉树
leetcode medium 106
与 从前中遍历中复原二叉树 同理，下文递归解法工夫复杂度和空间复杂度同为 O(N)。不同之处在于由后序遍历的后果数组的尾项确定为中序遍历的切分节点值。
const inorder = [...left0, root, ...right0]
const postorder = [...left1, ...right1, root]
最终失去以下实现代码：
func buildTree(inorder, postorder *[]int) *TreeNode {if len(inorder) < 1 || len(postorder) < 1 {return nil}
val := postorder[len(postorder)-1]
var i int
for ;i < len(inorder); i++ {if inorder[i] == val {break}
}
return &TreeNode{
Val: val,
Left: buildTree(inorder[:i], postorder[:i]),
Right: buildTree(inorder[i+1:], postorder[i:len(postorder)-1]),
}
}
演绎间接找到左右子树切分点的场景
在前文中，对于可间接找到左右子树切分点的场景可归纳如下：
1. 通过前序或后序遍历的后果数组，且依据前序遍历和后序遍历的定义，取前序遍历后果的首项或后序遍历后果的尾项，即为二叉树以后层的根节点；
1. 基于上步，遍历中序遍历后果，找到在中序遍历中的根节点，进而在中序遍历中划分左右子树所在的子数组；
1. 基于上步，且基于左右子树在 DFS 类型遍历中，仅有程序不同，后果数组项数始终统一（因为左右子树的节点数量在 DFS 的过程中恒定）的前提，那么可基于中序遍历后果的左右子树的子数组失去在前序或后序遍历后果数组中的左右子数组；
1. 基于上步，结构以后根节点和左右子树链接，并依据左右子树的数组递归结构左右子树。
func buildTree(preorderOrPostorder, inorder *[]int) *TreeNode {if len(preorderOrPostorder) < 1 || len(inorder) < 1 {return nil}
val := getNodeValFromPreorderOrPostorder(preorderOrPostorder)
var i int
for ; i < len(inorder); i++ {if inorder[i] == val {break}
}
return &TreeNode{
Val: val,
// make sure two sub slice should have same length
Left: buildTree(leftSubTreeInPreorderOrPostorder, leftSubTreeInInorder),
// make sure two sub slice should have same length
Right: buildTree(rightSubTreeInPreorderOrPostorder, rightSubTreeInInorder)
}
}
特地留神的是，在最初递归生成左右子树时，传入的子数组 肯定 要保障长度相等，且如果前文执行了正确的左右子树切分，递归时传入的子数组长度也 肯定 会相等（因为在 DFS 中左右子树在遍历的整个过程中节点数量恒定，那么遍历的后果长度相等，此处未思考原始二叉树中存在反复值的场景）。
从前后序遍历中复原二叉树
leetcode medium 889
与前后序和中序遍历搭配不同的是，在仅有前后序遍历的场景下，尽管可能失去根节点的值，但无奈立刻失去左右子树的切分点。回到对前后序遍历的定义中，有：
const preorder = [root, ...left0, ...right0]
const postorder = [...left1, ...right1, root]
借助以上构造，咱们转换一种思路，由原先依据根节点来确定左右子树的切分点的思考门路转换为由 左子树的第一项 来确定左右子树的切分点，即：
const preorder = [root, firstInLeftSubTree, ...otherLeft0, ...right0]
const postorder = [...otherLeft1, firstInLeftSubTree, ...right1, root]
依据前后序遍历的定义，能够失去的一个明确的推论是：在前序遍历中的左子树 第一个 节点 肯定 是在后序遍历中的左子树的 最初 一个节点（读者若对此推论不了解，能够画图了解）。据此，咱们失去在后序遍历后果中的左右子树的切分点。
func constructFromPrePost(pre, post *[]int) *TreeNode {if len(pre) < 1 || len(post) < 1 {return nil}
node := &TreeNode{Val: pre[0]}
if len(pre) == 1 || len(post) == 1 {return node}
var i int
for i = range post {
// compare with the first element of leftSubTree
if post[i] == pre[1] {
// shift to the first element of rightSubTreeInPost
i++
break
}
}
node.Left = constructFromPrePost(pre[1:i+1], post[:i])
node.Right = constructFromPrePost(pre[i+1:], post[i:len(post)-1])
return node
}
在递归构建左右子树时，首先在后序遍历的后果数组中依据先前失去的切分点，该切分点为前序遍历中左子树的第一项 firstInLeftSubTree 的值对应在后序遍历中的对应值的索引项的 下一项。切分失去左右子树所在的子数组，再依据失去的子数组在前序遍历的后果数组中失去左右子树的前序遍历后果，进而递归生成左右子树。
上文切分点为什么是 firstInLeftSubTree 在后序遍历中对应索引项的下一项？因为不像之前能间接依据根节点的值来失去残缺的左右子树所在子数组，依据前序遍历后果中的左子树第一项 firstInLeftSubTree 找到其在后序遍历中的索引时，保障的是在后序遍历中首项到第 i 项为左子树，那么第 i + 1 项才为右子树。
此递归解法的工夫复杂度的 worse case 为 O(N2)，空间复杂度的 worse case 为 O(N2)。
演绎生成二叉树的关键点
前文笔者大抵将依据任意两种 DFS 二叉树遍历的后果生成二叉树的场景分为以下两种子场景：
1. 间接依据根节点的值切分失去左右子树所在的子数组，依据子数组递归生成左右子树；
1. 无奈间接失去切分点的场景下，即依据前后遍历复原二叉树的场景下，依据前序遍历的左子树的第一项是后序遍历的右子树的最初一项的事实，失去切分左右子树的切分点。并依据失去的子数组生成左右子树。
从上文演绎能够失去，不论是在何种场景下，依据 DFS 二叉树遍历后果复原二叉树的 关键点 在于： 确定左右子树的切分点，进而失去左右子树的遍历后果，进而递归复原左右子树。