Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-02-28 14:38:02
652. Find Duplicate Subtrees
给你一个二元树,找出所有这个二元树的重复子树。
Example:
https://assets.leetcode.com/uploads/2020/08/16/e1.jpg
Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]
https://assets.leetcode.com/uploads/2020/08/16/e33.jpg
Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]
思路:
1.如果要判断两个树是否是一样,我们可以透过前序或后序走访所得到
的字串来判断(不可以是中序,忘记吃了一次WA ==)
2.dfs整个节点并把traversal出来的字串保存在一个Hash Table中,如果
这个表存在恰好两个的时候就表示当前的子树存在重复,只判断2是为了
去重。
3.遍历完整个树之后就完事了。
Java Code:
作者: idiont (supertroller)   2023-02-28 15:47:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com