左神算法基础提升--4

树形dp问题

求解这个问题需要用到我们在基础班上学到的从节点的左子树和右子树上拿信息的方法。
求最大距离主要分为两种情况：1.当前节点参与最大距离的求解；2.当前节点不参与最大距离的求解；
1.当前节点参与最大距离的求解的话，最大距离为左子树的高度加上右子树的高度加一；
2.当前节点不参与最大距离的求解的话，最大距离为左子树的最大距离与右子树的最大距离的最大值；
取这两种情况的最大值即为以当前节点为根节点的树的最大距离

核心代码

我们可以根据题意列出：
当某位员工参与时，派对的快乐值为其快乐值加上其直接下级员工不参与时的快乐值之和
当某位员工不参与时，派对的快乐值为其直接下级员工参与时的快乐值与其直接下级员工不参与时的快乐值的最大值之和。

代码：

Morris遍历

由上述规则可知：Morris遍历一共会来到某个节点两次，第一次到达某个节点时，其会找到其左子树的最右节点，将该节点的右指针指向当前节点，当其第二次来到节点时，其会将其左子树的最右节点指向空。由此我们便可以利用这一特点进行先序遍历和中序遍历。

先序遍历

中序遍历：

由于Morris遍历无法第三次回到某个节点，后序遍历会比较复杂：当第二次来到自己的时候，逆序打印其左树的右边界。