这是说法正确（用于确定一树是另一个子树）

Question

我有两个二叉树T1和T2，他们都是性格树木，这意味着：

struct TreeNode 
{ 
    char  data; 
    TreeNode* left; 
    TreeNode* right; 
    TreeNode(const char d, TreeNode* const lptr = NULL, 
          TreeNode* const rptr = NULL) 
     : data(d), left(lptr), right(rptr){} 

}; 

如果PreOrder2是PreOrder1和InOrder2的子串是InOrder1的子串，则T2是T1的子树。

上述说法是否正确？树平等的

定义：如果T1和T2具有完全相同的数据值和分配，然后T1 == T2，否则T1 != T2（NULL树木是相等的）。子树的

定义：如果在该T1N1 == T2存在至少一个节点N1，然后T2是T1的子树。

基本上，我不是在谈论节点地址的等价性;我正在谈论树的数据值和分布。

==编辑==

我认为这不是真的。有可能是T1中有两个子树，其中一个具有与T2相同的PreOrder，另一个具有与T2相同的InOrder。

现在我的问题变成：是否有一个简单的方法来确定T2是T1使用遍历的子树？

== EDIT ==

一个典型的例子，以使语句为false：

T1：

 A 
    B  C 
C   B 
D   D 

T2：

B 
C D 

另一个T1：

  A 
     A  A 
    B  B  C 
C   D  B 
D   C  D 

Answer 1

我一直在寻找一种算法来检查T2是否是一个小于O（m * n）的T1的子树。

经过一番搜索，我发现这两个线程：

Determine if a binary tree is subtree of another binary tree using pre-order and in-order strings

checking subtrees using preorder and inorder strings

看着这些可能实际上有可能找到只使用序和中序串子树。有趣的是，他们也在讨论有关子树的冲突定义。

不管怎样，我还没有测试这个方法，但你怎么试试这个？：

拼合树T1和T2为两个序和中序遍历字符串（就像我们在聊天谈到），但这次包括每一个NULL 离开琴弦在以及（例如，作为一个空格）和然后尝试检查一个子字符串。