Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

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：
-------------------------------------------
class Solution {
    private List<TreeNode> res;
    private Map<String, Integer> map;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        res = new ArrayList<>();
        map = new HashMap<>();
        dfs(root);
        return res;
    }
    private String dfs(TreeNode root) {
        if (root == null) {
            return "";
        }
        String tree = root.val + " " + dfs(root.left)
                               + " " + dfs(root.right);
        map.put(tree, map.getOrDefault(tree, 0) + 1);
        if (map.get(tree) == 2) {
            res.add(root);
        }
        return tree;
    }
}
-------------------------------------------

--
https://i.imgur.com/3e5CZfj.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677566285.A.BEE.html
推 idiont: 大師
推 NTHUlagka: 大師 為啥中序不行啊 這是什麼性質阿沒查到