9

好吧，今天面试被问到这个问题，大概是这样的：

“判断一棵二叉树是否包含在另一棵二叉树中（包含节点的结构和值的暗示）”

我想到了以下方法：

将较大的树展平为：

{{{-}a{-}}b{{-}c{-}}}d{{{-}e{{-}f{-}}}g{{{-}h{-}}i{{-}j{-}}}}

（我确实为此编写了代码，{-}意味着空的左子树或右子树，每个子树都包含在 {} 括号内）

现在对于较小的子树，我们需要匹配这个模式：

{{.*}e{.*}}g{{{.*}h{.*}}i{{.*}j{.*}}}

其中{.*}表示一个空的或非空的子树。

当时我想，这将是 java 中一个微不足道的正则表达式模式匹配问题，但我被迷惑了。实际上现在我觉得，我刚刚改变了问题（从另一个怪物中创造了一个怪物）。

是否有一个简单的正则表达式来匹配这些模式？我知道可能有其他方法可以解决这个问题，这可能不是最好的方法。我只是想知道这是否可以解决。

4

4 回答 4

1

我不确定面试官所说的“包含在另一个二叉树中”到底是什么意思。如果面试官要求一种方法来检查 A 是否是 B 的子树，这是一种根本不需要正则表达式的方法：

  • 使用前序遍历将树 A 和 B 展平以获取字符串，例如 preA 和 preB
  • 使用中序遍历将树 A 和 B 展平以获取字符串，例如 inA 和 inB
  • 确保在字符串中也包含空叶子（例如使用空格）
  • 检查 preA 是否是 preB 的子串并且 inA 是 inB 的子串

您想要包含空叶子的原因是因为当多个节点具有相同的值时，前序和中序可能不够。这是一个例子：

          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

可能有更好的方法，因为树比图更受限制和更简单。

于 2013-08-19T17:25:17.560 回答
0

严格来说，正则表达式不具备处理嵌套括号的能力。嵌套可以使用 递归正则表达式进行匹配，但 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是小树的大小。当大树和小树的每个元素都相等时，可以实现最坏的情况，并且小树实际上比大树大一个节点。

于 2013-08-19T18:18:45.393 回答
0

您可以使用其他答案中所述的子字符串检查来执行此操作，并且只使用一次遍历（前序、中序或后序），只要您打印树中每个节点的实体，不仅仅是他们的价值观。例如，二叉树是

  • 空树，我们将打印为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'的子树。

于 2013-08-19T17:49:28.327 回答
0

例如：- 请参阅随附的二叉树示例 T1 和 T2。

在此处输入图像描述

请注意，此问题与子树问题不同。binaryTree T2 包含在二叉树 T1 中，如果 T2 在 T1 中存在结构上完全相同的布局，并且 T1 可能包含额外的结构 [这无关紧要]。

我已经用下面的代码解决了这个问题。它有点太复杂了，无法解释，但请通过调试理解它。您调用函数的方式在下面的这一行。这里 tree1 是 T1 ， tree2 是 T2 ， size2 是 T2 树的大小。

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));
}
于 2020-10-11T03:57:58.990 回答