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