20250611题解

美食

前序遍历的最开始的节点是根节点，在中序遍历中找到这个节点，中序遍历可以被分为左右两部分。递归下去，就实现了二叉树的遍历。
关于第二问，二叉树的中序遍历的数量由其中只有一个子节点的节点数量x决定，为 $2^x$。
前序遍历和后序遍历不变，就算不知道中序遍历，但是树只有节点是偏向左或者右会有变化，所以我们只需要在第一问递归的时候求出有多少个只有一个子节点数目的节点就可以了。

行星碰撞

单调栈
我们从后往前把每个行星加入栈中，新加入的行星只会与原先的栈顶元素发生冲突，发生冲突后也只会与更前一个栈顶元素发生冲突，符合栈的性质

守护村庄

树的重心模板题
dfs，向上返回当前子树大小，每个节点都统计一下如果以当前点为重心，剩余连通块的最大块是多大，取最小值。
需要注意的是，搜索的时候求当前节点子树大小和sum，剩余部分n - sum - 1也是一个连通块。

odometer

数位dp，需要注意的是会有重复的情况，比如111222，这种数会被算两次，所以还要统计这种数的数量