java - 一段递归代码的问题

Question

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

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

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

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

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

Answer 1

まず第一に、この再帰関数には 4 つの可能な戻り値があることを理解する必要があります:

1. null は、この再帰がリーフ ノードに到達し、続行できないことを意味します。

2. p は、この再帰が p ノードに遭遇したことを意味します。

3. q は、この再帰が q ノードに遭遇したことを意味します。

4. lowestCommonAncestor は、見つかった最も低い共通祖先ノードを表します。

なぜそう言えるのでしょうか? 最初の 3 つの可能性は、コード
<1> if (!root || p == root || q == root) からわかるので、簡単に理解できるはずです。 ;
。

それではもう一度見てみましょう（省略します）
<2> left = lowerCommonAncestor(left, p, q);
<3> right = lowerCommonAncestor(right, p, q);
これらの 2 行です。実際の lowerCommonAncestor が見つかる前に、この関数は null、q、p のみを返す可能性があります。
これらの 2 行の判断をもう一度見てください
<4> if (left && left != p && left != q) return left;
<5> if (right && right != p && right != q) return right ;
<2><3>の戻り値がnull、p、qの場合、これら2つの判定の条件を満たさないため、戻りません。
それでは次の判断を入力する必要があります
<6> if (left && right) return root;
この文は何を意味しますか? <4>、<5>の判定からの戻りがない場合、左と右はnull、p、q、のいずれか1つしか取り得ないことを意味します
そして、ここでも左と右は非である必要があるという制限があります-null という意味です このとき、左右どちらか一方は p、もう一方は q でなければなりません。
このとき、このレベルの再帰関数のルート(このレベルの再帰関数であることに注意)は最低のCommonAncesstorなので、
それが返されます。
最後の文
<7> return left ? left : right;
これは、 left と right の少なくとも 1 つが null である場合、または
の両方が null である場合を意味します。 、nullを返します。

ここで、<2> と <3> の最も低い CommonAncesstor 再帰関数の呼び出しを見てください。これは、現在の
ノードの左側と右側でそれぞれ p と q を検索していると考えることができます。すると、4 種類の結果が得られます:

1. null を返し、p と q がこのブランチにまったく存在しないことを示します。

2. この分岐には p のみが存在し、q が存在しないことを示す p を返します。

3. q を返し、この分岐には q のみが存在し、p が存在しないことを示します。

4. lowerCommonAncessor に戻り、このブランチに p と q の両方が存在するため、それらの共通の祖先が見つかったことを示します。

私の言ったことは十分に徹底されていないかもしれませんが、お役に立てば幸いです:)

Answer 2

最初の条件はルートを判定すること、二番目は左を判定することです何か関係がありますか？