LeetCode 652: 尋找重複的子樹 Find Duplicate Subtrees

題目:

給定一棵二叉樹，傳回所有重複的子樹。對于同一類的重複子樹，你隻需要傳回其中任意一棵的根結點即可。

兩棵樹重複是指它們具有相同的結構以及相同的結點值。

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

示例 1：

1
       / \
      2   3
     /   / \
    4   2   4
       /
      4           

下面是兩個重複的子樹：

2
     /
    4           

和

4           

是以，你需要以清單的形式傳回上述重複子樹的根結點。

Therefore, you need to return above trees' root in the form of a list.

解題思路:

這就是一道考察二叉樹周遊的題, 周遊的時候序列化作為 String 類型存入 Map, 若其為第二次出現即将該結點加入數組.

代碼:

這裡以後序周遊為例, 需要注意葉子結點應當規定一個特殊字元作為替代 null 結點, 這裡用的是 '#'

Java:

class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();//待傳回數組
        if (root == null) return list;
        Map<String, Integer> map = new HashMap<>();//哈希映射查找重覆子結點
        traverse(root, map, list, "");
        return list;
    }
    //後序周遊
    private String traverse(TreeNode node, Map<String, Integer> map, List<TreeNode> list, String tree) {
        if (node == null) return tree + "#";
        String left = traverse(node.left, map, list, tree);//遞歸左子孩子
        String right = traverse(node.right, map, list, tree);//遞歸右子孩子
        tree = tree + node.val + left + right;//每個子樹路徑

        map.put(tree, map.getOrDefault(tree, 0) + 1);//存儲每個子樹路徑
        if (map.get(tree) == 2) list.add(node);//第二次出現相同路徑時存儲該結點
        return tree;
    }
}           

Python:

class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        res = [] # 待傳回數組
        if not root: return res
        hash_map = {} # 哈希映射查找重覆子結點
        self.traverse(root, hash_map, res, '')
        return res
    # 後序周遊
    def traverse(self, node: TreeNode, hash_map, res, tree):
        if not node: return tree + '#'
        left = self.traverse(node.left, hash_map, res, tree) # 遞歸左子孩子
        right = self.traverse(node.right, hash_map, res, tree) # 遞歸右子孩子
        tree = tree + str(node.val) + left + right # 每個子樹路徑
        if tree in hash_map.keys(): # 存儲每個子樹路徑
            hash_map[tree] += 1
        else:
            hash_map[tree] = 1
        if hash_map[tree] == 2: # 第二次出現相同路徑時存儲該結點
            res.append(node)
        return tree           

歡迎關注微信公衆号: 愛寫Bug