Java C++ 算法题解leetcode652寻找重复子树

题目描述

给定一棵二叉树，返回所有重复子树的根节点，这些子树重复出现在原始的二叉树中。重复的子树意味着在同一位置具有相同的结构以及相同的节点值。

思路分析

1. 我们需要类型为 Map 的一个 map，该 map 用于存储所有子树的出现次数。

2. 我们对二叉树做一次后序遍历，得到一个标识了每一个子树的字符串。对每一个子树的字符串，将该字符串存入 map 中，如果该字符串在 map 中已经存在，则其对应的值加 1。

3. 因为一个节点最多只能出现在一个子树中，所以只有当该节点的出现次数为 2 时，才需要将该子树的根节点加入到结果列表中。

代码实现

Java

class Solution {
    List<TreeNode> list = new ArrayList<>();
    Map<String, Integer> map = new HashMap<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        postOrder(root);
        return list;
    }

    public String postOrder(TreeNode node){
        if (node == null) {
            return "#";
        }
        String subTree = postOrder(node.left) + "," + postOrder(node.right) + "," + node.val;
        int count = map.getOrDefault(subTree, 0);
        if (count == 1) {
            list.add(node);
        }
        map.put(subTree, count + 1);
        return subTree;
    }
}

C++

class Solution {
private:
    unordered_map<string, int> map;
    vector<TreeNode*> res;
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        postorder(root);
        return res;
    }

    string postorder(TreeNode* node) {
        if (!node) {
            return "#";
        }
        string left = postorder(node->left);
        string right = postorder(node->right);
        string subTree = left + "," + right + "," + to_string(node->val);
        if (map[subTree] == 1) {
            res.push_back(node);
        }
        map[subTree]++;
        return subTree;
    }
};

示例说明

示例 1

输入

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

输出

   2
  / \
 4   4

说明

我们给出了两个相同的子树，分别是：

4

和

2
/ \
4   4

示例 2

输入

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

输出

4

说明

我们给出了两个相同的子树，分别是：

4

和

5

由于题目要求输出相同的子树的根节点，我们输出了根节点为 4 的子树。