检查二叉树是否有两个相同的子树
我想写一个方法来确定一棵树是否至少有一对相同的子树，这些子树的值和结构都必须相同。
假设给你一棵树，如下所示：
a
/ \
b f
/ / \
c g d
/ / /
d h e
/
e
这将返回true，因为我们有一对根为d的相同树。
我的想法是遍历每个节点，构建一个映射到树节点列表的节点名。在每次迭代中，我们检查当前节点名是否在映射中。如果它在中，那么我们可以调用布尔isSameTree（TreeNode t1，TreeNode t2）函数，对树节点列表中的每个节点使用当前节点，查看它们是否相同。
时间复杂度为O（n^3）。我想知道我们是否能做得更好！
共有1个答案
您的示例树也有一对具有roote的相同树。一般来说，如果两棵树是相同的，那么要么它们都是叶子，要么它们有相同的子树。因此，您可以将测试简化为检查原始树中的所有叶子是否是不同的，这需要O（n）哈希操作和平均情况θ（n）相等比较，除非哈希很差。
-
QSTN：当它是叶节点时，为什么需要初始化ls=0或rs=0。考虑链接中给出的树，如果我们到达节点4，如果(node==NULL isLeaf（node））返回1；上面的代码将1（true）返回到调用它的函数，即节点10，类似地，右侧将true返回到节点10，因此我们现在可以进入下面的循环，因为如果(isSumTree(node->left)&&isSumTree(node->left)&&isS
-
我实现了下面的C代码，以检查二叉树是否平衡，即左右子树的高度相差最多1。但是，我不确定它是否有效，或者以错误的方式重复检查子树。有人能引导我吗？
-
我正试图解决这个问题,但我遇到了一些麻烦： 在二进制搜索树(BST)中： 节点左子树中每个节点的数据值小于该节点的数据值。 节点右侧子树中每个节点的数据值大于该节点的数据值。 如您所见，节点（4）位于节点（3）的左侧子树中，尽管4大于3，因此方法应该返回。但是，我的代码返回。 我怎么能控制这个案子？如何检查左/右子树中的所有值都低于/大于根（不仅是直接子树）？
-
编写一个Lisp程序来检查一个二叉树是否是二叉搜索树。 我正在尝试编写一个二进制递归方法，但我是一个初学者，我不知道从这里去哪里。
-
我有一个很严重的问题，就是在一棵树中重复搜索子树。 我试过了，但是。。。 似乎没有正确的形式。containsTree函数在找到与另一个节点不同的节点时停止搜索。 下面是两棵树的例子。 在这种情况下，当函数比较右边的子树和左边的子树时，当find等于父节点但它有不同的子节点时，它会停止搜索。我需要函数不要停止搜索，而是抛出这一点，搜索所有其他子节点及其子树。