최근 공공 조상 시리즈
최근 공공조상 I
설명:
두 갈래 트리를 지정하여 두 노드의 가장 가까운 공통 부모 노드(LCA)를 찾습니다.최근 공공 조상은 두 노드의 공공 조상 노드이며 최대 깊이를 가지고 있다.
! :
예:
밑에 있는 이 두 갈래 나무에 대해
4
/ \
3 7
/ \
5 6
:
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
코드 구현:
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
if (root == null || root == A || root == B) {
return root;
}
//divide and conquer
TreeNode left = lowestCommonAncestor(root.left, A, B);
TreeNode right = lowestCommonAncestor(root.right, A, B);
if (left != null && right != null) {
return root;
}
if (left != null) {
return left;
}
if (left == null) {
return right;
}
return null;
}
}
최근 공공의 조상 II
설명:
두 갈래 나무와 두 갈래 나무 중 두 개의 노드를 주고 이 두 개의 노드를 찾은 최근 공공조상 LCA.두 노드의 최근 공공 조상은 두 노드의 모든 아버지 노드 중(이 두 노드 포함), 이 두 노드에서 가장 가까운 공공의 노드를 가리킨다.각 노드는 좌우 아들의 바늘을 제외하고 아버지의 바늘parent를 포함하여 자신의 아버지를 가리킨다.
예:
밑에 있는 이 두 갈래 나무에 대해
4
/ \
3 7
/ \
5 6
:
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
코드 구현:
/**
* Definition of ParentTreeNode:
*
* class ParentTreeNode {
* public ParentTreeNode parent, left, right;
* }
*/
public class Solution {
/**
* @param root: The root of the tree
* @param A, B: Two node in the tree
* @return: The lowest common ancestor of A and B
*/
public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
ParentTreeNode A,
ParentTreeNode B) {
ArrayList pathA = getPath2Root(A);
ArrayList pathB = getPath2Root(B);
int indexA = pathA.size() - 1;
int indexB = pathB.size() - 1;
ParentTreeNode lowestAncestor = null;
while (indexA >= 0 && indexB >= 0) {
if (pathA.get(indexA) != pathB.get(indexB)) {
break;
}
lowestAncestor = pathA.get(indexA);
indexA--;
indexB--;
}
return lowestAncestor;
}
private ArrayList getPath2Root(ParentTreeNode node) {
ArrayList path = new ArrayList<>();
while (node != null) {
path.add(node);
node = node.parent;
}
return path;
}
}
최근 공공의 조상 III
설명:
두 갈래 나무와 두 갈래 나무 중 두 개의 노드를 주고 이 두 개의 노드를 찾은 최근 공공조상 LCA.두 노드의 최근 공공 조상은 두 노드의 모든 아버지 노드 중(이 두 노드 포함), 이 두 노드에서 가장 가까운 공공의 노드를 가리킨다.null로 돌아가기 두 노드가 이 나무에 가장 가까운 공공 조상이 존재하지 않는다면.
예:
아래에 있는 이 나무를 보여주세요. 4
/ \
3 7
/ \
5 6
:
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
LCA(5, 8) = null
코드 구현:
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
class ResultType {
public boolean a_exist, b_exist;
public TreeNode node;
ResultType(boolean a, boolean b, TreeNode n) {
a_exist = a;
b_exist = b;
node = n;
}
}
public class Solution {
/**
* @param root The root of the binary tree.
* @param A and B two nodes
* @return: Return the LCA of the two nodes.
*/
public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
// write your code here
// write your code here
ResultType rt = helper(root, A, B);
if (rt.a_exist && rt.b_exist)
return rt.node;
else
return null;
}
public ResultType helper(TreeNode root, TreeNode A, TreeNode B) {
if (root == null)
return new ResultType(false, false, null);
ResultType left_rt = helper(root.left, A, B);
ResultType right_rt = helper(root.right, A, B);
boolean a_exist = left_rt.a_exist || right_rt.a_exist || root == A;
boolean b_exist = left_rt.b_exist || right_rt.b_exist || root == B;
if (root == A || root == B)
return new ResultType(a_exist, b_exist, root);
if (left_rt.node != null && right_rt.node != null)
return new ResultType(a_exist, b_exist, root);
if (left_rt.node != null)
return new ResultType(a_exist, b_exist, left_rt.node);
if (right_rt.node != null)
return new ResultType(a_exist, b_exist, right_rt.node);
return new ResultType(a_exist, b_exist, null);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
4
/ \
3 7
/ \
5 6
:
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
LCA(5, 8) = null
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
class ResultType {
public boolean a_exist, b_exist;
public TreeNode node;
ResultType(boolean a, boolean b, TreeNode n) {
a_exist = a;
b_exist = b;
node = n;
}
}
public class Solution {
/**
* @param root The root of the binary tree.
* @param A and B two nodes
* @return: Return the LCA of the two nodes.
*/
public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
// write your code here
// write your code here
ResultType rt = helper(root, A, B);
if (rt.a_exist && rt.b_exist)
return rt.node;
else
return null;
}
public ResultType helper(TreeNode root, TreeNode A, TreeNode B) {
if (root == null)
return new ResultType(false, false, null);
ResultType left_rt = helper(root.left, A, B);
ResultType right_rt = helper(root.right, A, B);
boolean a_exist = left_rt.a_exist || right_rt.a_exist || root == A;
boolean b_exist = left_rt.b_exist || right_rt.b_exist || root == B;
if (root == A || root == B)
return new ResultType(a_exist, b_exist, root);
if (left_rt.node != null && right_rt.node != null)
return new ResultType(a_exist, b_exist, root);
if (left_rt.node != null)
return new ResultType(a_exist, b_exist, left_rt.node);
if (right_rt.node != null)
return new ResultType(a_exist, b_exist, right_rt.node);
return new ResultType(a_exist, b_exist, null);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.