本文主要是介绍【LeetCode】升级打怪之路 Day 16：二叉树题型 —— 二叉树的构造，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今日题目：
- 654. 最大二叉树
- 105. 从前序与中序遍历序列构造二叉树
- 106. 从中序与后序遍历序列构造二叉树
- 889. 根据前序和后序遍历构造二叉树
目录
- LC 654. 最大二叉树 【easy】
- Problem：根据遍历序列来还原二叉树 【classic】 ⭐⭐⭐⭐⭐
- LC 105. 从前序与中序遍历序列构造二叉树
- LC 106. 从中序与后序遍历序列构造二叉树
- LC 889. 根据前序和后序遍历构造二叉树 【稍有难度】
今天主要练习了二叉树的构建的相关题目，典型的是从前序、中序、后序遍历的结果中的两个来还原一颗二叉树，这类题目的技巧类似，同时也是高频考题，需要重点掌握。
二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。
LC 654. 最大二叉树 【easy】
654. 最大二叉树
这个题目难度不大，但这个题经典地体现了使用递归的方法来构建一个二叉树。
Problem：根据遍历序列来还原二叉树 【classic】 ⭐⭐⭐⭐⭐
这类题目给出前序、中序、后序遍历的序列中的两个，要求来还原二叉树。
要使用分解问题的思路，着眼于如何构造一个二叉节点，然后递归地构建其左右子树。整体思路大致都是：
- 先从一个序列中确定出根节点的值，创建一个根节点
- 利用根节点的值，将两个序列切割成两部分，然后递归构建左右子树
具体在实现上，让我们从例题中具体学习。
LC 105. 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树
这个题目给出了前序遍历和中序遍历的结果，让我们还原二叉树。
这类题目首先画出一张图，便于我们确定切割的界限：
画了这张图后，我们就可以知道：
preorder的首元素就是 root- 利用 root 可以将
inorder切分出左子树和右子树，从而得知左子树的大小leftSize - 利用
leftSize，就可以将 preorder 也切分成左子树和右子树 - 将切分后的用于递归构建
代码示例：
这里有几个关键点：
build函数是主要逻辑所在，其参数包括了两个遍历序列及其范围，便于通过界定范围来递归构建左右子树- 先确定 root value，构建出 root，然后切分遍历序列并递归构建（计算出左子树大小
leftSize对于界定切分范围很有用） - 千万别把递归构建时的范围弄错了。有个验证的小技巧：
root.left的 build 中的范围、root、root.right的 build 的范围，这三者应该能够形成一个连续的区间。这个技巧对于检查以及防止多一个少一个这种失误很有用！
LC 106. 从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
学会了上一个题目后，这个题的套路一样，所以难度就不大了。代码上也和上一题差不多：
可以看到。套路基本一模一样。
LC 889. 根据前序和后序遍历构造二叉树 【稍有难度】
889. 根据前序和后序遍历构造二叉树
这个题目和前面有点变化了，前面两个题目给的序列可以唯一确定出一个二叉树，但这个题给的前序和后序无法唯一确定一个二叉树，原因就在于尽管我们可以确定出 root value，但无法通过 root valule 来进一步切分出序列中的左子树部分和右子树部分。
这个题目解题的诀窍在于：我们可以假定一个可以是 left node 的元素作为左子树，并利用它来切分序列。例如下面这个示例：
我们可以确定 3 是 root value，然后我们假定 preorder 中 root 的下一个元素 9 就是 left node，尽管它也可能是属于右子树。这种不确定也导致了给定的两个序列无法唯一确定一个二叉树。但幸运的是，我们只需要找到合法的一种可能就行，所以我们可以做出这种假设。
通过这种假设，我们就可以还原一棵二叉树了。这样，代码思路也就和前面两个题目一样了。代码如下：
可以看出，代码架构与之前的几乎一模一样。
这篇关于【LeetCode】升级打怪之路 Day 16：二叉树题型 —— 二叉树的构造的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
