Leetcode 652：为何中序遍历无法检测重复子树，前后序可以？

LeetCode 652题要求寻找二叉树中的重复子树，现有实现采用后序遍历将子树转换为字符串进行对比，代码如下：

class Solution {
public:
    vector<TreeNode*> ans;
    unordered_map<string, int> list;
    string helper(TreeNode* root){
        if(!root)return "";
        string cur = helper(root->left)+" "+helper(root->right)+" "+to_string(root->val);
        if(list[cur] == 1)ans.push_back(root);
        list[cur]++;
        return cur;
    }

    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        helper(root);
        return ans;
    }
};

但当尝试改用中序遍历时该方法失效，核心原因是中序遍历的字符串无法唯一确定一棵子树的结构，而前序/后序遍历的字符串可以唯一对应子树结构，具体原因如下：

• 中序遍历存在结构歧义：不同结构的子树可能生成完全相同的中序遍历字符串。比如：
  树A：

  1
     /
    2
  

  其中序遍历字符串为 "2 1"；
  树B：

  2
     \
      1
  

  其中序遍历字符串同样是 "2 1"。
  这两棵子树结构完全不同，但中序字符串一致，会被误判为重复。

• 前序/后序遍历能锁定结构：

  • 后序遍历是左子树字符串 + 右子树字符串 + 根节点值，左、右子树的结构已经由各自的遍历字符串确定，加上根的位置，整个子树的结构就唯一了——因为后序的顺序固定了根在左右子树之后，不会出现歧义。
  • 前序遍历是根节点值 + 左子树字符串 + 右子树字符串，同样根的位置在前，左右子树的结构信息完整，能唯一对应子树。

即使给空节点加上明确的标记（比如用#替代空字符串），中序遍历的结构歧义依然无法消除，因为它无法区分“根节点带左子树”和“根节点带右子树”这两种不同结构的情况。

内容的提问来源于stack exchange，提问作者Dying Falcon