2棵二叉树isSubtree函数的空间复杂度
2棵二叉树isSubtree函数的空间复杂度
提问于 2022-02-21 20:15:57
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
return areSame(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
public boolean areSame(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) return true;
if (root == null || subRoot == null) return false;
if (subRoot.val != root.val)
return false;
return areSame(root.left, subRoot.left) && areSame(root.right, subRoot.right);
}是上述解决方案的空间强制，以查找另一棵二叉树的树是子树 -O(高度(Tree1))(如大多数讨论注释中所建议的)还是O(高度(Tree1)+高度(Tree2))。
我认为应该是O(高度( tree1 )+高度(Tree2))，因为isSubtree可以像tree1的一个分支那样深入，而对于每个调用，isSame()可以和高度(Tree2)一样深，因此在任何时刻使用的最大堆栈内存将是ht1+ht2。
回答 1
Stack Overflow用户
回答已采纳
发布于 2022-02-21 21:15:06
假设布尔运算符&&和||是短路运算符(就像它们在Java中一样)，递归深度(和额外的堆栈内存)是由O(height(tree1))限制的。
因为isSubtree(root, subRoot)只能调用自己(第一棵树的高度减少了1)或areSame(root, subRoot)，并且最多一次从'isSubtree‘调用'areSame’可以在堆栈上(因为短路)，递归深度是O(height(tree1)) + max-depth-of(areSame(tree1, tree2))。
现在，如果areSame(root, subRoot)为null，则root不执行递归调用。如果root不是null，它可以调用：
areSame(root.left, subRoot.left) && areSame(root.right, subRoot.right);在这里，它只使用根节点的子节点调用areSame：第一棵树的高度被1降低了，第一次调用必须在第二次调用开始之前完成(因为&&短路)。因此，在调用堆栈上最多可以在任何时间对height(tree1) + 1调用areSame，因此isSubtree的总递归深度/堆栈空间为O(height(tree1))。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/71212513
复制相关文章
相似问题
腾讯云开发者
