java - 一段递归代码的问题

Question

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

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

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

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

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

Answer 1

First of all, you need to understand that there are 4 possible return values ​​of this recursive function:

1. null means that this recursion has hit the leaf node and cannot continue.

2. p means that this recursion has encountered the p node.

3. q, indicating that this recursion has encountered the q node.

4. lowestCommonAncestor, represents the lowest common ancestor node that has been found.

Why do you say this? You should understand the first three possibilities easily, because it can be seen from the line of code
<1> if (!root || p == root || q == root) return root;
.

Then look again (I’ll abbreviate it)
<2> left = lowestCommonAncestor(left, p, q);
<3> right = lowestCommonAncestor(right, p, q);
These two lines. Before the real lowestCommonAncestor is found, this function may only return null, q, p.
Look at these two lines of judgment again
<4> if (left && left != p && left != q) return left;
<5> if (right && right != p && right != q) return right ;
When the return values ​​of <2> and <3> are null, p, and q, the conditions for these two judgments cannot be met, so they will not be returned.
So we have to enter the next judgment
<6> if (left && right) return root;
What does this sentence mean? If there is no return from the judgment of <4>, <5>, it means that left and right can only be one of null, p, q,
And here it is also limited that left and right must be non-null, which means this At this time, one of left and right must be p and the other is q.
At this time, the root of the recursive function at this level (note that it is the recursive function at this level) is the lowestCommonAncesstor,
so it is returned.
The last sentence
<7> return left ? left : right;
Now that we are here, it means that at least one of left and right is null, then return the non-null one, or if both
are null, return null.

Now go back and look at the calls of the lowestCommonAncesstor recursive function at <2> and <3>. You can think of it as searching for p and q respectively in the left and right of the current
node. Then there are 4 kinds of results:

1. Returns null, indicating that p and q are not in this branch at all.

2. Return p, indicating that there is only p and no q in this branch.

3. Return q, indicating that there is only q in this branch and no p.

4. Return to lowestCommonAncesstor, indicating that there are both p and q in this branch, so their common ancestor has been found!

Maybe what I said is not thorough enough, I hope it will be helpful to you:)

Answer 2

The first condition is to determine root, and the second condition is to determine left. Is there any connection?