Open youngyangyang04 opened 5 months ago
另一个子树可以用KMP的思想来做。假设root的dfs遍历顺序(即前序遍历)是rootList,那么其子树subRoot的dfs遍历顺序subRootList一定是rootList的一个子串,因此可以用KMP匹配的思想来判断subRoot是不是root的子树。注意,在构建rootList的时候,左空子节点和右空子节点要区分开来
为啥树的题感觉这么难,简单题都感觉好难
@Chenromeo
为啥树的题感觉这么难,简单题都感觉好难
因为很多题目看着简单,但是你一写就是10+ms...树的题目必须要抠细节,有时候递归写出来看着很爽,实际上你的逻辑导致了很多重复遍历的结点
https://www.programmercarl.com/%E5%91%A8%E6%80%BB%E7%BB%93/20201003%E4%BA%8C%E5%8F%89%E6%A0%91%E5%91%A8%E6%9C%AB%E6%80%BB%E7%BB%93.html