Trouver deux nombres dans un arbre de recherche binaire qui s'ajoutent à un troisième nombre

Question

Vous obtenez un BST de nombres. Vous devez y trouver deux nombres (a, b) tels que a + b = S, en temps O (n) et O (1).

Quel pourrait être l'algorithme?

Une façon possible pourrait être deux convertir la BST à une liste doublement chaînée et puis à partir de l'avant et à la fin:

if front + end > S then end-- 

Ou:

if front + end < S then front++ 

Answer 1

Comme mentionné précédemment, vous ne pouvez pas résoudre ceci dans un espace O (1) constant.De plus, toutes les autres solutions actuellement proposées utilisent au moins un espace O (log^2 n), et non O (log n): la pile a des trames O (log n) et chaque trame a un pointeur de taille O (log n). Maintenant, la solution actuellement acceptée par @ dharm0us détruit le BST en le convertissant en un tableau. Ceci est inutile. Au lieu de cela, utilisez deux itérateurs, l'un effectuant une traversée dans l'ordre et l'autre effectuant une traversée d'ordre inverse, et recherchez deux nombres identiques à ceux d'un tableau. Chaque itérateur a une pile avec des trames O (log n) avec chaque trame contenant un pointeur de taille O (log n) pour l'espace total O (log^2 n). L'heure est clairement linéaire O (n).

Answer 2

Essayez que je le pouvais, je Je ne suis pas sûr que cela soit possible avec un arbre binaire sans pointeur parent. O(1) espace signifie que vous ne pouvez ni utiliser la récursivité (la croissance de la pile est O(log n)) ni la copier dans une liste doublement chaînée (O(n)).

La méthode que vous faites allusion à est une solution de complexité temporelle O(n) mais pas avec un arbre binaire normal. En fait, j'ai répondu à une question similaire dans les moindres détails here. Cela a été résolu avec O(n) espace mais seulement parce qu'ils n'ont pas été initialement triés.

est possible avec un arbre contenant des pointeurs parents. Si les nœuds enfants ont des pointeurs vers leurs parents, vous pouvez essentiellement traiter l'arbre comme une liste doublement liée traitée de manière itérative. Pour ce faire, exécutez le pointeur de départ vers le nœud le plus à gauche et le pointeur de fin vers le nœud le plus proche. Vous gardez également deux variables pour stocker le dernier mouvement (en haut ou en travers, initialement en haut) de chaque pointeur afin que vous puissiez sélectionner intelligemment le prochain mouvement (les front++ et end-- dans votre question). Ensuite, vous pouvez utiliser les pointeurs en cours et les derniers mouvements, avec la somme en cours, pour décider du pointeur à déplacer (et comment).

Answer 3

Cette question m'a récemment été posée lors d'une interview. Quand j'étais coincé, on m'a donné un indice.

Astuce: Supposons que vous ayez à résoudre ce même problème pour un tableau trié, comment le résoudriez-vous alors?

Me: Conservez deux pointeurs. Un au début, un autre à la fin. Si la somme des éléments de ces pointeurs est inférieure à la somme requise, déplacez le pointeur avant vers la droite, sinon déplacez le pointeur arrière vers la gauche. Interviewer: Comment pourriez-vous faire la même chose pour un arbre de recherche binaire? Me: Effectuez une traversée d'ordre et enregistrez les pointeurs sur les noeuds d'un tableau. Et utilisez la même logique que dans le cas des tableaux.

Interviewer: Oui, cela fonctionne. Mais la complexité de l'espace est O (n). Pourriez-vous le réduire?

Moi (après beaucoup de temps): Ok, convertissez le BST dans une liste doublement liée, en utilisant this algo. Et puis utilisez la même logique que dans le cas de tableau. La comlexité spatiale sera O (lg (n)) en raison de la récursivité.