c - 如何查看2个二叉树是否相似？

Question

我需要检查两个二叉树，看看它们是否相似...意思是它们是否具有完全相同的结构，然后数据位于相同的级别(但数据不需要处于相同的结构) ...

示例

     A               A
  |     |         |     |
  B     C         C     B
 | |   | |       | |   | |
 D E   F G       G D   E F

左边的二叉树与右边的相似(显然有很多变化!)

这是我迄今为止的伪代码:

if( tree1 == NULL && tree2 == NULL ) return TRUE;

if( tree1 == NULL || tree2 == NULL ) return FALSE;

if( tree1->label != tree2->label ) return FALSE;

return (   TRUE
        && (  (   similarTrees(tree1->left, tree2->left)
               && similarTrees(tree1->right, tree2->right))
            || (   similarTrees(tree1->left, tree2->right)
                && similarTrees(tree1->right, tree2->left))  ));

我的推理是，既然两个左子树可以相等，两个右子树可以相等，或者一个树的左右子树和另一个子树的左右子树可以相等，那么这个逻辑递归应该有效...然而，事实并非如此。

similarTree是递归函数

感谢您的帮助!

Answer 1

代码和示例不匹配。

如果每个子树包含相同的根标签和相同的子树(尽管顺序是任意的)，则代码假定树是相等的。

另一方面，该示例并不适用于此。例如，在左侧树中，C 的子级是 F 和 G，而在右侧 G 和D。

要编写代码来检查它们是否相似，您必须首先明确定义相似的含义。例如。两棵树中是否都存在标签。它应该存在于同一级别吗？它可以发生多次吗？