左神算法——二叉树进阶
二叉树进阶
树形dp的套路
可能性罗列，左右树分别可能收集什么样的信息
过程总结
例题
问题1
规定 距离 是二叉树中任意连个node之前的node数量加上二者本身的数量和
求一棵二叉树中的最大距离
分析
问题拆解，每一个子问题可以看做是1，不考虑根节点的距离，2，必须纳入根节点的距离
前者是根节点两棵子树的最大距离，后者是左右子树的高度和，由此对于树形dp套路中问左右字数要内容的结构就包含自己的最大值和高度。
代码
问题2
一家公司人员结构可以看做一棵多叉树结构，每个人结构中包含一个int类型的欢乐值和下级，现在需要开一个排队，需要达到要求来人让欢乐值最大，但是员工的直接上下级不能同时出现。
分析
还是从每一棵子树上进行分解，将这棵子树的欢乐值情况列举出来，首先是根节点来的情况，那么所有直接子节点就不来，然后是根节点不来的情况，最大欢乐值就变成了看每棵子树或者不来的最大值，因此可以由此确定返回值的结构，双int，分别代表根节点来或不来的最大欢乐值。
注意在遇见题目的时候不要跳过条件分解这一大前提，直接按照经验去构造解题过程必然会导致带着优化代码的目的去再次审题，容易陷入误区，建议还是跟着步骤走：分析条件，得出结构，编写代码。
代码
Morris遍历
概念
一种遍历二叉树方式，时间复杂度为O(N)，空间复杂度为O(1)
通过利用原树中大量空闲指针的方式，达到节省空间的目的
本质上这是一种通过改变节点指向来遍历的方法，所以具体使用还需要看题目要求，而且一般这个方法多用在面试
细节
实质
这种遍历实质上是对递归过程的模拟，在一个递归过程中，一个节点一共会被访问三次，这些是被通过递归过程的返回操作完成的，
Morris则是利用右node对cur的关联性进行访问，一旦访问一个node 的右节点，那么这node就彻底回不去了
代码
时间复杂度
先中后序遍历加工
先序
对于所有位置，只能到达一次，直接打印，如果能达到两次，第一次打印
中序遍历
只经历一次的节点，直接打印，会经历两次的节点，第二次打印
由于这俩是直接在原有的Morris上更改的，只展示不同的地方
因为图中的continue会让在能经过两地的node略过本次循环内容，不会触碰到打印行为
后序遍历
流程是对于所有只能到一次的数不管，在第二次的到达可以到两次的数时，执行步骤1，当左子树右边界处理完后，执行步骤2
如何逆序打印左子树右边界
单链表的逆序操作
后序遍历代码实现
Morris遍历应用
判断二叉树是不是搜索二叉树
二叉树递归套路和Morris是不是最优解
解题方法中必须要对第三次回到节点有强制要求，选用递归套路；如果没有这种要求，Morris是最优解
