二叉树的判断

二叉树的判断

判断一颗二叉树是不是搜索二叉树

（左边的比根小，右边的比根大）

中序遍历一下，如果是的话就一定是升序的

如何判断一颗二叉树是否是完全二叉树

1.遍历任意的节点时候，如果返回右孩子没有左孩子，返回false

2.在第一个条件不违规的条件下，如果遇到第一个左右孩子不全的情况，那么接下来遇见的节点都是叶节点，否则为false。

queue.isEmpty()判断queue是否为空

if（l == null || r == null）{

lead = true;

} 每一步都会进行这个判断，如果上面返回的是false，那么当满足这个条件的时候依旧会改成true；

如何判断一棵树是否是平衡二叉树

1.左右子树的高度差不超过1（|右高-左高|

定义返回是否是平的，高度是多少

二叉树套路(树型DP)

使用搜索二叉树，搜索二叉树的条件，左树上面的最大值小于根节点，右树上面的最小值大于根节点，我们需要得到的条件是左树是否搜索，以及最大数，右树需要得到的条件是是否搜索，以及最小数。但是这个不能满足递归的条件，所以我们统一获取到这个数的三个值，是否是搜索数，最大值和最小值

如何判断一棵树是满二叉树

1.第一种方法，最大深度L 节点数 N，当满足N = 2^L - 1 的时候肯定是满二叉树

树型DP可以通过向左树和右树要信息，解题的可以用这种方法

给定两个二叉树的节点node1和node2，找到他们的最低公共祖先节点

两个节点最初汇聚的点就是最低公共祖先

还有很难理解的一种写法，但是很牛逼

后继节点，中序遍历中，一个节点的后一个节点

给一个头节点的指针，想如何不去遍历整个树用一个O（N）复杂度，而是想要走K步就去写一个O（K）就能弄成的代码

找X的后继

1.X有右树的时候，那么他的后继节点就是他右树上面的最左节点

2.X无右树

二叉树的序列化和反序列化

内存里的一颗树如何变成字符串形式，又如何从字符串形式变成内存里的树

先把数进行序列化，可以用特殊符号进行分割

然后进行反序列化，根据下划线做值的分割

折纸游戏