Najniższy wspólny przodek rozwiązania Leetcode drzewa binarnego

Poziom trudności Średni
Często zadawane pytania Amazonka Apple ByteDance Facebook Google Intuit Karat LinkedIn Microsoft wyrocznia Palantir Technologies PayPal Spotify Yandex
Drzewo binarne Głębokie pierwsze wyszukiwanie Sumologiczna Drzewo Globalna technologia Walmartodwiedzajacy 55

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W ramach projektu Najniższy wspólny przodek Drzewo binarne Rozwiązanie LeetCode – „Najniższy wspólny przodek drzewa binarnego” stwierdza, że ​​dany korzeń drzewa binarnego i dwa węzły drzewa. Musimy znaleźć najniższego wspólnego przodka tych dwóch węzłów.

Najniższy wspólny przodek (LCA) dwóch węzłów  p i q jest najniższym węzłem w drzewie binarnym, który ma oba  p i q jako jego potomkowie.

Przykład:

Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

Wyjaśnienie:

Najniższy wspólny przodek rozwiązania Leetcode drzewa binarnegoszpilka

  • Sprawdź powyższy diagram, aby lepiej zrozumieć.
  • Najniższy węzeł, którego potomkami jest węzeł 5 i węzeł 1, to węzeł o wartości 3.
Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5

Wyjaśnienie:

Najniższy wspólny przodek rozwiązania Leetcode drzewa binarnegoszpilka

  • Sprawdź powyższy diagram, aby lepiej zrozumieć.
  • Najniższym wspólnym przodkiem jest sam węzeł o wartości 5.

Podejście

Idea:

  1. Główną ideą rozwiązania tego problemu jest użycie Rekurencja.
  2. Z przypadek podstawowy, gdy węzeł główny staje się wskaźnikiem o wartości null, zwracaj root bez zmian.
  3. Ilekroć mamy węzeł główny albo równy węzłowi p albo równy węzłowi q, dobrze zwróć węzeł główny ponieważ obecny węzeł może być naszym najniższym wspólnym przodkiem.
  4. Ponadto, ilekroć mamy węzeł zwrócony z lewego poddrzewa, a prawe poddrzewo nie jest wskaźnikami zerowymi, zwrócimy bieżący węzeł, który jest naszym najniższym wspólnym przodkiem.
  5. Gdy wszystkie powyższe przypadki zawiodą, sprawdź, czy węzeł zwrócony z lewego poddrzewa nie jest wskaźnikiem zerowym, zwróć ten węzeł, w przeciwnym razie zwróć węzeł zwrócony z prawego poddrzewa.

Kod

Najniższy wspólny przodek drzewa binarnego Rozwiązanie 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;
    }
};

Najniższy wspólny przodek drzewa binarnego Rozwiązanie 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;
    }
}

Analiza złożoności dla najniższego wspólnego przodka rozwiązania Leetcode drzewa binarnego

Złożoność czasowa

Złożoność czasowa powyższego kodu wynosi NA) ponieważ przechodzimy raz przez całe drzewo wejściowe w najgorszym przypadku, gdzie N = całkowita liczba węzłów w drzewie.

Złożoność przestrzeni

Złożoność przestrzeni powyższego kodu wynosi O(1) [bez uwzględniania rekurencyjnego miejsce na stos].

Wywiady dotyczące projektowania systemu pękania
Translate »