java - 一段递归代码的问题

问题描述

在一篇博客上看到了一个递归函数，但我感觉划线的那一行似乎永远不为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) return root;这行代码可以看出来。

那么再看（我就简写了）<2> left = lowestCommonAncestor(left, p, q);<3> right = lowestCommonAncestor(right, p, q);这两行。在真正的lowestCommonAncestor被找到之前，这个函数只可能会返回null，q，p。再看这两行判断<4> if (left && left != p && left != q) return left;<5> if (right && right != p && right != q) return right;当<2>，<3>两处的返回值是null，p，q的时候，这两处判断的条件都无法满足，所以不会返回。所以要进入再下面的判断<6> if (left && right) return root;这句什么意思？如果从<4>，<5>的判断处没有返回，说明left和right只能是null，p，q中的一个，而这里了又限定了left和right必须是非null，意思就是这时候left和right必定一个是p，一个是q。那么这个时候，本层递归函数的root（注意是本层递归函数）就是那个lowestCommonAncesstor，于是就返回它。最后一句<7> return left ? left : right;既然到了这里，就说明left和right里面至少有一个是null，那么就返回非null的那个，或者如果两个都是null就返回null。

现在倒回去再看一下lowestCommonAncesstor这个递归函数在<2>，<3>两处的调用，你可以把它看成是去当前节点的left和right中分别去寻找p，和q，那么无非结果有4种：

返回null，说明p，q根本不在这个分支中。

返回p，说明这个分支中只有p，没有q。

返回q，说明这个分支中只有q，没有p。

返回lowestCommonAncesstor，说明这个分支中既有p又有q，于是就已经找到他们的公共祖先啦！

可能说的还是不够透彻，希望对你有帮助：）

第一个条件是判断root，第二个是判断left，有什么联系吗？