java - 一段递归代码的问题

Question

在一篇博客上看到了一个递归函数，但我感觉划线的那一行似乎永远不为true呢？

因为函数里的第一个判断条件：

if (!root || p == root || q == root) return root;

就决定了left必定是p,q,null之一吧？

我对递归的理解不太深刻,不知道理解的对不对？谢谢。

Answer 1

Tout d'abord, vous devez comprendre qu'il existe 4 valeurs de retour possibles de cette fonction récursive :

1. null, indiquant que cette récursivité a atteint le nœud feuille et ne peut pas continuer.

2. p, indiquant que cette récursion a rencontré le nœud p.

3. q, indiquant que cette récursion a rencontré le nœud q.

4. lowestCommonAncestor, indiquant le nœud ancêtre commun le plus bas trouvé.

Pourquoi dites-vous cela ? Vous devriez comprendre facilement les trois premières possibilités, car à partir de
<1> if (!root || p == root || q == root) return root;
Cette ligne de code est visible.

Regardez à nouveau (je vais l'abréger)
<2> left = lowerCommonAncestor(left, p, q);
<3> right = lowerCommonAncestor(right, p, q);
Ces deux lignes. Avant que le véritable lowerCommonAncestor ne soit trouvé, cette fonction ne peut renvoyer que null, q, p.
Regardez ces deux lignes pour juger à nouveau
<4> if (left && left != p && left != q) return left;
<5> && right != q) return right;
Lorsque les valeurs de retour de <2> et <3> sont nulles, p, q, les conditions de ces deux jugements ne peuvent pas être remplies, donc ce ne sera pas le cas. est revenu.
Nous devons donc saisir le prochain jugement
<6> if (left && right) return root;
Que signifie cette phrase ? S'il n'y a pas de retour du jugement de <4>, <5>, cela signifie que gauche et droite ne peuvent être que nul, p, q,
et ici il est également limité que gauche et droite doivent être non nul, ce qui signifie qu'à ce moment, l'un de gauche et de droite doit être p et l'autre est q.
À l'heure actuelle, la racine de la fonction récursive à ce niveau (notez qu'il s'agit de la fonction récursive à ce niveau) est le plus basCommonAncesstor,
elle est donc renvoyée.
La dernière phrase
<7> return left ? left : right;
Maintenant que nous sommes ici, cela signifie qu'au moins l'une de gauche et de droite est nulle, puis renvoie celle qui n'est pas nulle, ou si les deux
Si tous sont nuls, renvoyez null.

Maintenant, revenez en arrière et regardez les appels de la fonction récursive lowerCommonAncesstor dans <2> et <3>. Vous pouvez considérer cela comme une recherche de p à gauche et à droite du nœud
actuel. et q, alors il y a quatre types de résultats :

1. Renvoie null, indiquant que p et q ne sont pas du tout dans cette branche.

2. Renvoie p, indiquant qu'il n'y a que p et pas de q dans cette branche.

3. Renvoie q, indiquant qu'il n'y a que q dans cette branche et pas de p.

4. Renvoie le plus basCommonAncesstor, indiquant qu'il y a à la fois p et q dans cette branche, donc leur ancêtre commun a été trouvé !

Peut-être que ce que j'ai dit n'est pas assez complet, j'espère que cela vous sera utile :)

Answer 2

La première condition est de déterminer la racine, et la deuxième condition est de déterminer la gauche. Y a-t-il une connexion ?