leetcode 236 Lowest Common Ancestor of a Binary Tree
来源：1-1 为什么要研究树结构
weixin_慕圣6334738
2021-08-09 10:54:56
老师您好，这道题目我看了一下您的解法，但是有一点不是特别明白
我不太明白的点在于 if(root == p || root == q)，为什么 当root等于其中的某一个的时候就直接返回root了，照理说题目给q，p两点，如果说root是其中的某一点就直接返回的话，怎么确保root下面还有另外一个点呢～
ps：看了您的很多解法发现都相当聪明，想顺便请教一下老师您拿到一个树的题目时，解题思路是怎样的～怎样才能确保我写recursion的时候没有遗漏掉某些逻辑
1回答
-
liuyubobobo
2021-08-09
lowestCommonAncestor(root, p, q) 的函数语义是：在以 root 为根的树中，找 p 和 q 的 lca，p 和 q 一定在这棵子树中。
所以，如果 root 就是 p，那么 q 在这棵子树中，p 和 q 的 lca 就是 root，也就是就是 p；
同理：如果 root 就是 q，那么 p 在这棵子树中，p 和 q 的 lca 就是 root，也就是就是 q；
否则的话，p 和 q 的 lca 肯定不是 root，有可能在当前 root 的左子树中，也有可能在当前 root 的右子树中，递归去找。
==========
“怎样才能确保我写recursion的时候没有遗漏掉某些逻辑”
我没有特别特殊的方法。我也怀疑根本不存在这样的方法，我一说，你一听，树的递归问题就完全没有问题了。
我只能说：
1）遇到树的问题，九成九有递归性质，挖掘递归性质；
2）书写递归函数，一定要明确递归函数的宏观语义。这在我来看是最最重要的。在我看来，80% 的 bug 来源，是语义不清，无论是函数的语义，还是变量的语义。
在这个基础上，只能多看多练。你提出的问题都不错，相信你是有进步的：）
继续加油！：）
0
相似问题