二叉树心法（构造篇）

AI summary

type

status

date

slug

summary

654. 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。

每个二叉树节点都可以认为是一棵子树的根节点，对于根节点，首先要做的当然是把想办法把自己先构造出来，然后想办法构造自己的左右子树。

所以，我们要遍历数组把找到最大值 maxVal，从而把根节点 root 做出来，然后对 maxVal 左边的数组和右边的数组进行递归构建，作为 root 的左右子树。

使用遍历的方式，直接看代码：

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

面试笔试中常考的题目。

类似上一题，我们肯定要想办法确定根节点的值，把根节点做出来，然后递归构造左右子树即可。

我们先来回顾一下，前序遍历和中序遍历的结果有什么特点？

找到根节点是很简单的，前序遍历的第一个值 preorder[0] 就是根节点的值。

关键在于如何通过根节点的值，将 preorder 和 inorder 数组划分成两半，构造根节点的左右子树？

换句话说，对于以下代码中的 ? 部分应该填入什么：

对于左右子树对应的 inorder 数组的起始索引和终止索引比较容易确定，就是 rootVal 的两边。

对于 preorder 数组呢？如何确定左右数组对应的起始索引和终止索引？

这个可以通过左子树的节点数推导出来，假设左子树的节点数为 leftSize，那么 preorder 数组上的索引情况是这样的：

另外，通过 for 循环遍历的方式去确定 index 效率不算高，可以进一步优化。因为题目说二叉树节点的值不存在重复，所以可以使用一个 HashMap 存储元素到索引的映射，这样就可以直接通过 HashMap 查到 rootVal 对应的 index 。

完整代码如下：

我们的主函数只要调用 buildTree 函数即可，你看着函数这么多参数，解法这么多代码，似乎比我们上面讲的那道题难很多，让人望而生畏，实际上呢，这些参数无非就是控制数组起止位置的，画个图就能解决了。

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

类似的，看下后序和中序遍历的特点：

整体的算法框架和上一题非常类似，这里直接给出代码：

有了前一题的铺垫，这道题很快就解决了，无非就是 rootVal 变成了最后一个元素，再改改递归函数的参数而已，只要明白二叉树的特性，也不难写出来。

889. 根据前序和后序遍历构造二叉树

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中任何一个。

这道题和前两道题有一个本质的区别：

通过前序中序，或者后序中序遍历结果可以确定唯一一棵原始二叉树，但是通过前序后序遍历结果无法确定唯一的原始二叉树。

举个例子，比如给你这个输入：preorder = [1,2,3], postorder = [3,2,1]，下面这两棵树都是符合条件的，但显然它们的结构不同：

不过话说回来，用后序遍历和前序遍历结果还原二叉树，解法逻辑上和前两道题差别不大，也是通过控制左右子树的索引来构建：

首先把前序遍历结果的第一个元素或者后序遍历结果的最后一个元素确定为根节点的值。

然后把前序遍历结果的第二个元素作为左子树的根节点的值。

在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引边界，进而确定右子树的索引边界，递归构造左右子树即可。

直接上代码：

代码和前两道题非常类似，我们可以看着代码思考一下，为什么通过前序遍历和后序遍历结果还原的二叉树可能不唯一呢？

关键在这一句：leftRootVal = preorder[preStart + 1];

我们假设前序遍历的第二个元素是左子树的根节点，但实际上左子树有可能是空指针，那么这个元素就应该是右子树的根节点。由于这里无法确切进行判断，所以导致了最终答案的不唯一。

另外，需要多加一个 base case：preStart == preEnd ，因为代码中有 leftRootVal = preorder[preStart + 1] ，如果不加这个会数组越界。