Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/02/28 14:38)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串253/719 (看更多)

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