시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
또한 의 가장 낮은 공통 조상 이진 트리 LeetCode 솔루션 – "이진 트리의 가장 낮은 공통 조상"은 이진 트리의 루트와 트리의 두 노드가 주어졌음을 나타냅니다. 이 두 노드의 가장 낮은 공통 조상을 찾아야 합니다.
두 노드의 가장 낮은 공통 조상(LCA) p 및 q 이진 트리에서 가장 낮은 노드는 둘 다 p 및 q 그 후손으로.
예:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
설명 :
- 더 나은 이해를 위해 위의 다이어그램을 확인하십시오.
- 노드 5와 노드 1을 자손으로 갖는 가장 낮은 노드는 값이 3인 노드입니다.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
설명 :
- 더 나은 이해를 위해 위의 다이어그램을 확인하십시오.
- 가장 낮은 공통 조상은 자체 값이 5인 노드입니다.
접근
아이디어 :
- 이 문제를 해결하기 위한 주요 아이디어는 재귀.
- 와 더불어 기본 케이스, 루트 노드가 널 포인터가 되면 루트를 있는 그대로 반환합니다.
- 루트 노드가 있을 때마다 노드 p와 같거나 노드 q와 동일, 우리는 루트 노드를 반환 현재 노드가 가장 낮은 공통 조상이 될 수 있기 때문입니다.
- 또한 왼쪽 하위 트리에서 반환된 노드가 있고 오른쪽 하위 트리가 null이 아닌 포인터일 때마다 가장 낮은 공통 조상인 현재 노드를 반환합니다.
- 위의 모든 경우가 실패하면 왼쪽 하위 트리에서 반환된 노드가 널 포인터가 아닌지 확인하고 해당 노드를 반환하고 그렇지 않으면 오른쪽 하위 트리에서 반환된 노드를 반환합니다.
암호
이진 트리 Leetcode C++ 솔루션의 가장 낮은 공통 조상:
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr){
return root;
}
TreeNode* l = lowestCommonAncestor(root->left,p,q);
TreeNode* r = lowestCommonAncestor(root->right,p,q);
if(root==p or root==q or (l!=nullptr and r!=nullptr)){
return root;
}
return l==nullptr?r:l;
}
};
바이너리 트리 Leetcode Java 솔루션의 가장 낮은 공통 조상:
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return root;
}
TreeNode l = lowestCommonAncestor(root.left,p,q);
TreeNode r = lowestCommonAncestor(root.right,p,q);
if(root==p || root==q || (l!=null && r!=null)){
return root;
}
return l==null?r:l;
}
}
이진 트리 Leetcode 솔루션의 가장 낮은 공통 조상에 대한 복잡성 분석
시간 복잡성
위 코드의 시간 복잡성은 의 위에) N = 트리의 총 노드 수인 최악의 경우 전체 입력 트리를 한 번 탐색하기 때문입니다.
공간 복잡성
위 코드의 공간 복잡성은 다음과 같습니다. O(1) [재귀를 고려하지 않고 스택 공간].
