6. 图
Tags:
如何判断一颗二叉树是否是搜索二叉树？ 搜索二叉树的中序遍历的结果一定不是降序的。
用模板： 判断一个树是不是搜索二叉树，对每个节点需要满足：左边是搜索，右边是搜索，左 max<当前节点，右 min 小于当前节点
而递归需要返回相同的值，所以每个节点的递归需要返回 1. 是不是搜索 2 当前子树的最小 3 当前子树的最大
树的递归，按照如下的方法进行考虑
- 分解成子问题，每个树，我需要知道子树的什么信息就能解决当前的子问题了? 注意递归返回的信息不管左右树都应该是一样，如果需要的信息左右树的不一样，就全都返回来（先当成黑盒）
- 根据拿到的信息，在后序的位置解决这个子问题（可能需要很多种判断）
- 制作当权节点的返回值，需要和1中信息是一样的
- 想一想 base case 的返回值应该是什么。如果不知道base case返回什么，就可以试试返回空，然后在后序的位置拿到信息后判断一下。
- 递归调用就行了
上面的这个思路还能解决所有解决树型 DP 的算法（二叉树中最难的问题）
树型DP：你的问题可以通过向左树要信息，向右数要信息来解决，那就是树型DP
如何判断一颗二叉树是完全二叉树？ 宽度遍历，遍历的时候如果出现了： a. 如果有右孩子但是没有左孩子，直接返回 fale b. 在满足a的情况下，如果遇到了第一个左右两个孩子双全的情况，那么接下来遇到的所有节点必须是叶节点
如何判断一颗二叉树是满二叉树 一种麻烦的方法：先求最大深度，再求节点个数。因为满二叉树的节点个数是 2^最大深度-1 = 节点个数
如何判断一颗二叉树是否是平衡二叉树 条件为 3 个：左子树平衡，右子树平衡，|左子树高度-右子树高度| ⇐ 1
因此左右树都需要返回两个信息：1. 是否平衡 2. 高度是多少
利用后序做