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(height(tree1)) （如大多數討論評論中所建議的那樣）或 O(height(tree1) height(tree2))在哪里
我認為它應該是 O(height(tree1) height(tree2)) 因為isSubtree可以深入到 tree1 的一個分支，并且對于每次呼叫，isSame() 可以深入到 height(tree2)，所以最大值任何時候使用的堆疊記憶體都是 ht1 ht2。
uj5u.com熱心網友回復：
假設布爾運算子&&和||是短路運算子（就像它們在 Java 中一樣），遞回深度（和額外的堆疊記憶體）的上限為O(height(tree1)).
由于isSubtree(root, subRoot)只能呼叫自身（第一棵樹的高度減1）或areSame(root, subRoot)，并且一次最多可以直接從'isSubtree'呼叫'areSame'一次在堆疊上（因為短路），遞回深度是O(height(tree1)) max-depth-of(areSame(tree1, tree2))。
現在，如果為 null ，areSame(root, subRoot)則不進行遞回呼叫。root如果root不為空，它可能會呼叫：
areSame(root.left, subRoot.left) && areSame(root.right, subRoot.right);
在這里，它只呼叫areSameroot 的子節點：第一棵樹的高度減少了1，并且第一次呼叫必須在第二次呼叫開始之前完成（因為&&短路）。所以在任何時候呼叫堆疊上最多可以height(tree1) 1呼叫areSame，所以總遞回深度/堆疊空間isSubtree是O(height(tree1))
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/430689.html