LeetCode二叉树题目：
- 105.【从前序与中序遍历序列构造二叉树】
解题思路：1、明确根节点要做的事情：将前序遍历的第一个元素作为根，找到左子树个数和右子树个数；2、通过前序遍历方式，将二叉树还原 - 106.【从中序与后序遍历序列构造二叉树】
解题思路：1、明确根节点要做的事情：将前序遍历的最后一个元素作为根，找到左子树和右子树个数；2、通过前序遍历方式，还原二叉树 - 297.【序列化二叉树】
- 652.【寻找重复的子树】
解题思路：1、明确根节点需要做的事情：根节点需要做两个事，第一个获取该节点的数的序列化结构，第二个判断有无其他重复子树。序列化很简单，主要如何判断其他重复子树。如果要判断其他子树，我们需要使用一个数据结构来存储序列化的子树，让每个节点把自己子树的序列化结果存进去，这样，对于每个节点，就可以知道有没有其他节点的子树和自己重复了。首先想到使用HashSet结构进行存储，但是有个问题如果出现多棵重复的子树，结果集res中必然出现重复，而题目要求不希望出现重复。我们可以将HashSet升级成HashMap，不仅存储重复子树，还存储子树出现次数，即可解决该问题。
二叉搜索树(BST)
- 二叉搜索树(BST)定义：
1、对于 BST 的每一个节点node，左子树节点的值都比node的值要小，右子树节点的值都比node的值大。
2、对于 BST 的每一个节点node，它的左侧子树和右侧子树都是 BST。 - 二叉搜索树有个很重要的特性：BST的中序遍历，一定是有序的，并且是升序。如果改变遍历左右子树的顺序，也可以让其变为降序
- LeetCode题目：
- 230.【二叉搜索树中第K小的元素】
解题思路：注意，不是最高效解法，仅仅是熟悉BST中序遍历特性。利用BST中序遍历后，查找。- BST中序遍历解决该问题的优化：
上述没有优化时，会遍历所有的节点时间复杂度为O(n)。我们优化后，时间复杂度为O(logn)。
优化思路：BST之所以查询很快，就是因为它有左节点一定大于根节点，并且右节点一定大于根节点的特性。如果我们可以在BST的节点中添加一个记录自己排名的信息size，当k==size，说明该节点就是目标节点；k<size，则目标节点一定在左子树中；k>size，则目标节点一定在右树中。优化后，不用遍历全部节点，因此时间复杂度为O(logn)
- BST中序遍历解决该问题的优化：
- 538.【把二叉搜索树转换为累加树】/1038.【把二叉搜索树转换为累加树】
解题思路：先考虑下，能否通过传统二叉树问题来解，即确定每个节点应该做的事。首先，可能会想到让每个节点的值=右树总值+当前节点的值，但是这种没考虑到父节点的值也可能大于当前节点，也需要加上。我们根据BST中序遍历的特性，如果使用降序的中序遍历，就可以很轻松的解决该问题。 - 接下来几个二叉搜索树的题，属于巩固和强化。判断合法性和删除挺难的。
- 98.【验证二叉搜索树】
解题思路：先按照二叉树基本思路来思考，首先，可能考虑根节点和左节点、右节点比较，但是这种没有考虑到BST是针对整个树来说的，因此我们需要将root的约束传递到root的左右子树。所以我们需要一个辅助函数，增加参数列表。 - 700.【二叉搜索树中的搜索】
- 在BST中插入一个值
- 在BST中删除一个值
- 230.【二叉搜索树中第K小的元素】
京公网安备 11010502036488号