在一篇博客上看到了一个递归函数，但我感觉划线的那一行似乎永远不为true呢？
因为函数里的第一个判断条件：
if (!root || p == root || q == root) return root;就决定了left必定是p,q,null之一吧？
我对递归的理解不太深刻,不知道理解的对不对？谢谢。
迷茫2017-04-18 10:55:18
首先你要弄明白，这个递归函数的返回值有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，于是就已经找到他们的公共祖先啦！
可能说的还是不够透彻，希望对你有帮助：）
