寻找重复子树

题目描述

  给定一颗二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
  两颗树重复是指它们具有相同的结构以及相同的结点值。

输入输出样例

输入：
        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4
输出：
      2
     /
    4
	与
	4

题解

  题目的描述可能有点令人困惑，但是通过对上例的全面分析后，你大概就可以明白题目的含义了。

  首先，节点4本身也可以作为一棵子树，在这棵二叉树中就存在了许多重复的4节点。

  此外，这棵二叉树中同样也存有了重复的以2为节点的子树。

  那么对应的数组中就应该存有2,4这两个节点了

  既然理解题目了就可以动手解题了，对于二叉树问题。还是一个套路，先思考对应的节点应该做什么事情。如果想要知道以自己为根的子树是否重复，是否应该被加入结果列表中?
  很明显，我需要知道以下两点：

1. 以我为根的的这棵二叉树(子树)长什么样子？
2. 以其他节点为根的子树都长什么样子？

  那么现在的问题又变成了如何确定以自己为根的二叉树长什么样子？这里我们可以使用后序遍历，原因是它的遍历顺序不正好是[左、右、根]。这样不正好符合我们的需求吗。
  这道题目，可以通过使用字符串拼接来完成。以”#”表示空节点，接着按照后序遍历完成拼接。对于第一个问题解决了，那么如何知道自己长成什么样子的？这个我们可以通过unorder_map去重。对于每个出现过的字符串进行记录。具体代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 class Solution {
public:
    vector<TreeNode*> res;
    unordered_map<string,int> ansmap;
    string encode(TreeNode* root) {
        if (root == nullptr) return "#";
        string l = encode(root->left);
        string r = encode(root->right);
        string ans = to_string(root->val) + ',' + l + ',' + r;
        if (ansmap[ans] == 1) res.push_back(root);
        ansmap[ans]++;
        return ans;
    }
	vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
       if (!root) return {};
       encode(root);
       return res; 
    }
};