一段递归代码的问题

  • Z时代
  • 2024-01-10
  • 分类：IT

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

图片描述

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

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

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

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

回答：

首先你要弄明白，这个递归函数的返回值有4种可能：

  1. null，表示这次递归已经碰到叶子节点，无法再继续下去了。

  2. p，表示这次递归已经碰到p节点了。

  3. q，表示这次递归已经碰到q节点了。

  4. 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种：

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

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

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

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

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

回答：

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

以上是 一段递归代码的问题 的全部内容， 来源链接： utcz.com/p/190766.html

回到顶部