이진 트리 Leetcode 솔루션의 가장 낮은 공통 조상

난이도 중급
자주 묻는 질문 아마존 Apple ByteDance Facebook 구글 인튜이트 캐럿 링크드인 Microsoft 신탁 Palantir Technologies 페이팔 스포티 파이 Yandex 주차
이진 트리 깊이 우선 검색 서모로직 나무 월마트 글로벌 테크조회수 55

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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

설명 :

이진 트리 Leetcode 솔루션의 가장 낮은 공통 조상

  • 더 나은 이해를 위해 위의 다이어그램을 확인하십시오.
  • 노드 5와 노드 1을 자손으로 갖는 가장 낮은 노드는 값이 3인 노드입니다.
Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5

설명 :

이진 트리 Leetcode 솔루션의 가장 낮은 공통 조상

  • 더 나은 이해를 위해 위의 다이어그램을 확인하십시오.
  • 가장 낮은 공통 조상은 자체 값이 5인 노드입니다.

접근

아이디어 :

  1. 이 문제를 해결하기 위한 주요 아이디어는 재귀.
  2. 와 더불어 기본 케이스, 루트 노드가 널 포인터가 되면 루트를 있는 그대로 반환합니다.
  3. 루트 노드가 있을 때마다 노드 p와 같거나 노드 q와 동일, 우리는 루트 노드를 반환 현재 노드가 가장 낮은 공통 조상이 될 수 있기 때문입니다.
  4. 또한 왼쪽 하위 트리에서 반환된 노드가 있고 오른쪽 하위 트리가 null이 아닌 포인터일 때마다 가장 낮은 공통 조상인 현재 노드를 반환합니다.
  5. 위의 모든 경우가 실패하면 왼쪽 하위 트리에서 반환된 노드가 널 포인터가 아닌지 확인하고 해당 노드를 반환하고 그렇지 않으면 오른쪽 하위 트리에서 반환된 노드를 반환합니다.

암호

이진 트리 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) [재귀를 고려하지 않고 스택 공간].

균열 시스템 설계 인터뷰
Translate »