每日一题总结, 9.24-10.08.
LCP 19. 秋叶收藏集
有点分情况讨论Dp的意思,对于dp问题我们还是需要分两步分析,首先分析子问题是什么。我们最终的结果是长度为n
的树叶中,得到上下上的形式。这个问题可以变为子问题。在长度为n-1
的树叶集得到 1. 上下上/上下,这样最后一个只需要保证变为上;这样我们考虑第n-1
片叶子,如果n-1
是上下上,则n-2
需要是 上下或者上下上;如果n-1
是上下,则n-2
需要是 上上或者上下。
因此实际上由三个大的状态:上,上下,上下上。
1 | class Solution { |
834. 树中距离之和
基本思路是树形dp,并且很巧妙的用了换根的方法,降低了复杂度。
有一个很好的题解。
我理解的思路就是,首先不可避免的需要遍历一遍树也就是dfs完成,这样可以得到根节点的边数量,然后再遍历一遍各个节点,计算出基于已知根节点情况下,自己的距离之和。
每个大根节点的边数量 = 根节点连接的所有子节点数量+所有子节点作为子树的大根的距离之和。
每个子节点的距离之和 = 当前节点作为子树的大根节点的距离之和 +(父节点 - 当前节点的贡献)
1 | class Solution { |
145. 二叉树的后序遍历
递归的方法很常见了,这里还是记录下递归方法
1 | # 迭代方法: |