使用预序遍历和字符串方法展平二叉树来寻找子树？

Question

最近，我运行研究了这个解决方案，用于查找提供的树是否是更大树的子树：

https://discuss.leetcode.com/topic/88700/easy-o-n-java-solution-using-preorder-traversal

该解决方案非常直观且富有创意，因此我实现了它的递归版本以供自己借鉴；但我发现自己想知道为什么同样的解决方案不适用于 post-ordering 或 in-ordering.

这是我尝试通过 LeetCode 的所有测试用例的 C++ 解决方案：

class Solution {
public:
    std::string s1;
    std::string s2;

    void generatePreOrder(TreeNode *root, std::string &s)
    {
       if (root == 0)
       {
           s+=std::string(",#");
           return;
       }
       s+=std::string(",");
       s+=std::string(std::to_string(root->val));
       generatePreOrder(root->left, s);
       generatePreOrder(root->right, s);
    }
    bool isSubtree(TreeNode* s, TreeNode* t) {
        generatePreOrder(s, s1);
        generatePreOrder(t, s2);
        int pos = s1.find(s2);
        return (!(pos == std::string::npos));
    }
};

从根本上说，我们似乎只是将树展平为字符串，然后使用字符串比较函数来查找树之间的相似性。所以，我想只要两棵树之间的排序一致，这三种排序方案中的任何一种都应该可以正常工作。但是，当我更改解决方案以使其按顺序执行时：

 ...
    void generateInOrder(TreeNode *root, std::string &s)
    {
       if (root == 0)
       {
           s+=std::string(",#");
           return;
       }
       generateInOrder(root->left, s);
       s+=std::string(",");
       s+=std::string(std::to_string(root->val));
       generateInOrder(root->right, s);
    }
 ...

该解决方案未能通过所有 LeetCode 案例。这是因为这种方法行之有效吗？或者只是LeetCode练习机制的一个漏洞，整个方法都有缺陷？

Answer 1

当您包含空值时，每棵不同形状的树都会产生唯一的前序或后序遍历。

这对于中序遍历来说是不正确的，它总是以 null 开始，以 null 结束，并在 null 和节点之间交替。

例如，这些树：

  B          D    
 / \        / \
A   D      B   E
   / \    / \
  C   E  A   C

都生产

,#,A,#,B,#,C,#,D,#,E,#

使用预序遍历和字符串方法展平二叉树来寻找子树？

Using pre-order traversal and string methods to flatten binary tree to find subtrees?

algorithm

binary-tree

tree-traversal