가장 낮은 공통 조상
설명
이진 트리root와 정수a 및 b가 주어지면 a 및 b가 하위 항목으로 있는 가장 낮은 노드의 값을 찾습니다. 노드는 자신의 자손이 될 수 있습니다.
트리의 모든 노드는 고유한 것으로 보장됩니다.
제약 조건:
n ≤ 100,000 여기서 n는 root의 노드 수입니다.예 1
입력
root = [0, [1, null, null], [2, [6, [3, null, null], [4, null, null]], [5, null, null]]]
a = 3
b = 5
산출
2
예 2
입력
root = [0, [1, null, null], [2, [6, [3, null, null], [4, null, null]], [5, null, null]]]
a = 6
b = 4
산출
6
직관
DFS
구현
import java.util.*;
/**
* public class Tree {
* int val;
* Tree left;
* Tree right;
* }
*/
class Solution {
public int solve(Tree root, int a, int b) {
return lca(root, a, b).val;
}
private Tree lca(Tree root, int a, int b) {
if (root == null) {
return null;
}
if (root.val == a || root.val == b) {
return root;
}
Tree left = lca(root.left, a, b);
Tree right = lca(root.right, a, b);
if (left != null && right != null) {
return root;
} else if (left != null) {
return left;
} else if (right != null) {
return right;
} else {
return null;
}
}
}
시간 복잡도
import java.util.*;
/**
* public class Tree {
* int val;
* Tree left;
* Tree right;
* }
*/
class Solution {
public int solve(Tree root, int a, int b) {
return lca(root, a, b).val;
}
private Tree lca(Tree root, int a, int b) {
if (root == null) {
return null;
}
if (root.val == a || root.val == b) {
return root;
}
Tree left = lca(root.left, a, b);
Tree right = lca(root.right, a, b);
if (left != null && right != null) {
return root;
} else if (left != null) {
return left;
} else if (right != null) {
return right;
} else {
return null;
}
}
}
Reference
이 문제에 관하여(가장 낮은 공통 조상), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/jiangwenqi/lowest-common-ancestor-4cg2텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
