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

2019 年 11 月 20 日
筆記

題目:

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

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

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

和

因此，你需要以列表的形式返回上述重複子樹的根結點。

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