微信绑定网站,《网站基础建设-首保》,电脑网页打不开是什么问题,文本分析网站文章目录 树形dp问题Morris遍历 树形dp问题 求解这个问题需要用到我们在基础班上学到的从节点的左子树和右子树上拿信息的方法。 求最大距离主要分为两种情况#xff1a;1.当前节点参与最大距离的求解#xff1b;2.当前节点不参与最大距离的求解#xff1b; 1.当前节点参与最… 文章目录 树形dp问题Morris遍历 树形dp问题 求解这个问题需要用到我们在基础班上学到的从节点的左子树和右子树上拿信息的方法。 求最大距离主要分为两种情况1.当前节点参与最大距离的求解2.当前节点不参与最大距离的求解 1.当前节点参与最大距离的求解的话最大距离为左子树的高度加上右子树的高度加一 2.当前节点不参与最大距离的求解的话最大距离为左子树的最大距离与右子树的最大距离的最大值 取这两种情况的最大值即为以当前节点为根节点的树的最大距离 核心代码 我们可以根据题意列出 当某位员工参与时派对的快乐值为其快乐值加上其直接下级员工不参与时的快乐值之和 当某位员工不参与时派对的快乐值为其直接下级员工参与时的快乐值与其直接下级员工不参与时的快乐值的最大值之和。 代码 Morris遍历 由上述规则可知Morris遍历一共会来到某个节点两次第一次到达某个节点时其会找到其左子树的最右节点将该节点的右指针指向当前节点当其第二次来到节点时其会将其左子树的最右节点指向空。由此我们便可以利用这一特点进行先序遍历和中序遍历。 先序遍历 中序遍历
由于Morris遍历无法第三次回到某个节点后序遍历会比较复杂当第二次来到自己的时候逆序打印其左树的右边界。
