Tree_Graph에서 T2가 T1의 하위 트리인지 여부@CareerCup
You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1
번역:
두 그루의 큰 두 갈래 나무가 있다. T1은 수백만 개의 결점이 있고 T2는 수백 개의 결점이 있다.쓰기 프로그램은 T2가 T1의 하위 트리인지 여부를 판단합니다.
아이디어:
1) 중순 전순 순으로 한 그루의 나무를 결정하기 때문에 두 그루의 중순 전순을 모두 쓴다. 만약 두 개의 역순 중 T2가 모두 T1의 자열이라면 T2가 T1의 자수임을 확정할 수 있다.
물론 구분이 안 되는 경우도 있을 거예요.
의 경우... 때문에
T1, in order: 3,3 T1, pre order 3,3
T2, in order: 3,3 T2, pre order 3,3
그래서 반드시null 노드에 포함시켜야 하기 때문에
T1, in order: 0, 3, 0, 3, 0 T1, pre order 3, 3, 0, 0, 0
T2, in order: 0, 3, 0, 3, 0 T2, pre order 3, 0, 3, 0, 0
이런 방법은 시간 복잡도: O(n+m), 공간 복잡도: O(n+m), n, m는 각각 두 나무의 노드수이다.대량의 데이터가 있을 때 적용되지 않습니다!
2) 귀속!뿌리 노드에서 아래로 내려가 자수가 왼쪽 자수나 오른쪽 자수 안에 존재하는지 판단한다.
시간 복잡성:
O(nm), 공간 복잡성:
O(log(n) + log(m))
그러나 실제로 실제 운행할 때 귀환은 하위 트리의 조건을 충족시키는 것을 발견하면 바로 귀환하고 계속 찾지 않는다.따라서 귀속법은 실제에서 시간과 공간을 막론하고 더욱 좋다!
package Tree_Graph;
import CtCILibrary.AssortedMethods;
import CtCILibrary.TreeNode;
public class S4_8 {
// t2 t1
public static boolean isSubTree(TreeNode t1, TreeNode t2) {
if(t2 == null) { //
return true;
}
if(t1 == null) { // r2 ,
return false;
}
if(t1.data == t2.data) { //
if(isSameTree(t1, t2)){
return true;
}
}
// r1
return isSubTree(t1.left, t2) || isSubTree(t1.right, t2);
}
//
public static boolean isSameTree(TreeNode t1, TreeNode t2) {
if(t1==null && t2==null) {
return true;
}
if(t1==null || t2==null) {
return false;
}
if(t1.data != t2.data) {
return false;
}
return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);
}
public static void main(String[] args) {
// t2 is a subtree of t1
int[] array1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
int[] array2 = {2, 4, 5, 8, 9, 10, 11};
TreeNode t1 = AssortedMethods.createTreeFromArray(array1);
TreeNode t2 = AssortedMethods.createTreeFromArray(array2);
if (isSubTree(t1, t2))
System.out.println("t2 is a subtree of t1");
else
System.out.println("t2 is not a subtree of t1");
// t4 is not a subtree of t3
int[] array3 = {1, 2, 3};
TreeNode t3 = AssortedMethods.createTreeFromArray(array1);
TreeNode t4 = AssortedMethods.createTreeFromArray(array3);
if (isSubTree(t3, t4))
System.out.println("t4 is a subtree of t3");
else
System.out.println("t4 is not a subtree of t3");
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.