84669 人が学習中
152542 人が学習中
20005 人が学習中
5487 人が学習中
7821 人が学習中
359900 人が学習中
3350 人が学習中
180660 人が学習中
48569 人が学習中
18603 人が学習中
40936 人が学習中
1549 人が学習中
1183 人が学習中
32909 人が学習中
在一篇博客上看到了一个递归函数,但我感觉划线的那一行似乎永远不为true呢?
因为函数里的第一个判断条件:
if (!root || p == root || q == root) return root;
就决定了left必定是p,q,null之一吧?
我对递归的理解不太深刻,不知道理解的对不对?谢谢。
闭关修行中......
まず第一に、この再帰関数には 4 つの可能な戻り値があることを理解する必要があります:
null は、この再帰がリーフ ノードに到達し、続行できないことを意味します。
p は、この再帰が p ノードに遭遇したことを意味します。
q は、この再帰が q ノードに遭遇したことを意味します。
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 行の判断をもう一度見てください if (left && left != p && left != q) return left; if (right && right != p && right != q) return right ;<2><3>の戻り値がnull、p、qの場合、これら2つの判定の条件を満たさないため、戻りません。 それでは次の判断を入力する必要があります 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 種類の結果が得られます:
null を返し、p と q がこのブランチにまったく存在しないことを示します。
この分岐には p のみが存在し、q が存在しないことを示す p を返します。
q を返し、この分岐には q のみが存在し、p が存在しないことを示します。
lowerCommonAncessor に戻り、このブランチに p と q の両方が存在するため、それらの共通の祖先が見つかったことを示します。
私の言ったことは十分に徹底されていないかもしれませんが、お役に立てば幸いです:)
最初の条件はルートを判定すること、二番目は左を判定することです何か関係がありますか?
まず第一に、この再帰関数には 4 つの可能な戻り値があることを理解する必要があります:
null は、この再帰がリーフ ノードに到達し、続行できないことを意味します。
p は、この再帰が p ノードに遭遇したことを意味します。
q は、この再帰が q ノードに遭遇したことを意味します。
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 行の判断をもう一度見てください
if (left && left != p && left != q) return left;
if (right && right != p && right != q) return right ;
<2><3>の戻り値がnull、p、qの場合、これら2つの判定の条件を満たさないため、戻りません。
それでは次の判断を入力する必要があります
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 種類の結果が得られます:
null を返し、p と q がこのブランチにまったく存在しないことを示します。
この分岐には p のみが存在し、q が存在しないことを示す p を返します。
q を返し、この分岐には q のみが存在し、p が存在しないことを示します。
lowerCommonAncessor に戻り、このブランチに p と q の両方が存在するため、それらの共通の祖先が見つかったことを示します。
私の言ったことは十分に徹底されていないかもしれませんが、お役に立てば幸いです:)
最初の条件はルートを判定すること、二番目は左を判定することです何か関係がありますか?