大家好，今天我在面试中被问到了这个问题：
“判断一个二叉树是否包含在另一个二叉树中（包含意味着节点的结构和值都相同）”
我想到了以下方法：
将较大的树展平为：
{{{-}a{-}}b{{-}c{-}}}d{{{-}e{{-}f{-}}}g{{{-}h{-}}i{{-}j{-}}}}
{-}表示空的左子树或右子树，每个子树都被包含在{}括号中）{{.*}e{.*}}g{{{.*}h{.*}}i{{.*}j{.*}}}
其中{.*}表示空或非空子树。
当时我以为这将是Java中一个微不足道的正则表达式模式匹配问题，但我被搞糊涂了。现在实际上我感到，我只是把问题转化了（从一个问题中创造出另一个怪物）。
是否有一个简单的正则表达式一行来匹配这些模式？我知道可能有其他方法来解决这个问题，而这可能不是最好的方法。我只是想知道这是否可以解决。
你想要包括空叶子节点的原因是，当多个节点具有相同的值时，前序和中序可能不足够区分。以下是一个示例：
A
A A
B B C
C D B
D C D
您还可以查看以下内容：
此外，阅读以下内容以获取有关二叉树的前序遍历和中序遍历的更多信息：
http://en.wikipedia.org/wiki/Tree_traversal
现在，如果他不仅指子树，那么问题可能会更加复杂，这取决于面试官所说的“部分”是什么意思。你可以将问题看作是一个子图同构问题（树只是图的子集），这是NP完全问题。http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem
可能有更好的方法，因为树比图形受限制且更简单。
(value <left> <right>)是值为value且左右子树字符串分别为<left>和<right>的节点，那么单个子字符串检查就足够了吗？ - Joshua TaylorB 为根节点且 A 为左子节点的树是 (B A nil)，以 A 为根节点且 B 为右子节点的树是 (A nil B)。有了标点符号，我认为不需要两次遍历。（请注意，这仍然可以使用中序遍历完成，因为 (A B nil) 和 (nil A B) 也是不同的。） - Joshua Taylor您可以使用子字符串检查（如其他答案中所述），并仅使用一个遍历（前序、中序或后序），只要您打印树中每个节点的完整性，而不仅仅是它们的值。例如，二叉树可以是：
null，或者(value left-tree right-tree)，其中left-tree和right-tree被替换为左子树和右子树的表示。现在，每棵树都有一个明确的打印表示，因此如果树T的字符串表示是树S的子字符串，则树T是树S的子树。
例如，该树为
A
/ \
B C
/ \
D E
被表示为
(A (B (D null null) (E null null)) (C null null))
你可以检查这棵树的子树是否有字符串
(A (B (D null null) (E null null)) (C null null))
(B (D null null) (E null null))
(D null null)
(E null null)
(C null null)
每个子树都是字符串的子串。
当然，唯一需要注意的是值的字符串表示与树的序列化干扰的情况（例如，值字符串包含空格或括号等），因此为了使其更加健壮，您需要采取适当的分隔符或转义措施。
还要注意的是，并非每个作为树的子串的字符串都对应于树的子树。例如，字符串null) (E是树的子串，但不对应于树的子树；只有当字符串s是树t的表示时，如果s是树t'的字符串s'的子串，则t是t'的子树。
严格来说，正则表达式并不适用于处理嵌套括号。可以使用递归正则表达式来匹配嵌套，但Java的正则表达式引擎不支持递归表达式。在PERL或PHP中，您可以使用类似以下的模式：
{(?:(?R)|-)}\w{(?:(?R)|-)}
为了匹配某些树形结构，但您仍然无法指定特定级别的子节点的值。
因此，不幸的是，没有简单的一行正则表达式可以解决这个问题。正则表达式不是您需要的工具。
为了回答这个问题，我建议构建您的大树和小树，然后使用以下类调用largeTree.contains(smallTree)：
public class BTreeNode
{
public String value;
public BTreeNode left;
public BTreeNode right;
public bool contains(BTreeNode tree)
{
bool retVal = visit(tree, this);
if (!retVal && left != null)
retVal = left.contains(tree.left);
if (!retVal && right != null)
retVal = right.contains(tree.right);
return retVal;
}
private bool visit(BTreeNode small, BTreeNode large)
{
bool retVal;
if (small == null)
{
retVal = true;
}
else if (small.value.equals(large.value))
{
retVal = visit(small.left, large.left) && visit(small.right, large.right);
}
else
{
retVal = false;
}
return retVal;
}
}
O(m * log n)，其中m是大树的大小，n是小树的大小。当大树和小树的每个元素都相等，并且小树实际上比大树多一个节点时，就会达到最坏情况。
return(containsInternal(tree1.getRoot(), tree2.getRoot(), size2));
// This function checks if the node1 is contained with in another binary tree with starting point of node2 [ which means node1->m_data==node2->m_data has been verified ].
// This is not same as subtree problem. Read the code carefully.
bool checkContains(const BinaryTreeNode<int>* node1, const BinaryTreeNode<int>* node2, long& iterations)
{
if(iterations<0)
return(true);
if(!node1)
return(true);
bool returnStatus1=true, returnStatus2=false, returnStatus3=true;
if(node1->m_leftChild)
{
if(!node2->m_leftChild)
return(false);
else
returnStatus1=checkContains(node1->m_leftChild, node2->m_leftChild, iterations);
}
//cout<<"Attempting to compare "<<node1->m_data<<" and "<<node2->m_data<<" with iterations left = "<<iterations<<endl;
if(node1->m_data==node2->m_data)
{
returnStatus2=true;
--iterations;
}
if(node1->m_rightChild)
{
if(!node2->m_rightChild)
return(false);
else
returnStatus3=checkContains(node1->m_rightChild, node2->m_rightChild, iterations);
}
return(returnStatus1&&returnStatus2&&returnStatus3);
}
// Iterate tree starting at node1 in in order traversal and if node matches node of tree2 then start doing contains checking further.
bool containsInternal(const BinaryTreeNode<int>* node1, const BinaryTreeNode<int>* node2, long size)
{
if(!node1||!node2)
return(false);
bool result1=containsInternal(node1->m_leftChild, node2, size);
bool result2=false;
if(node1->m_data==node2->m_data)
result2=checkContains(node2, node1, size); // Note : node2 is passed first argument since checkContains traverses structure of BT of first argument.size is size of tree of node2.
bool result3=containsInternal(node1->m_rightChild, node2, size);
return(result1||result2||result3);
}
// Checks if the tree2 is a part of the tree1.
bool contains(BinaryTree<int>& tree1, BinaryTree<int>& tree2)
{
size_t size1=tree1.size();
size_t size2=tree2.size();
if(!size2)
return(true); // null tree is always contained in another tree.
if(size2>size1)
return(false); // The tree2 can not be inside tree1 if it is bigger in size.
return(containsInternal(tree1.getRoot(), tree2.getRoot(), size2));
}