【C++二叉树】236.二叉树的最近公共祖先
·
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
思路分析：
公共祖先满足的特征：
- p是q的孩子，则q是祖先，反之亦然。
- p和q是“我”的左子树和右子树中的节点，则“我”是祖先。（如题目中给的示例）
情况一：如果树为二叉搜索树
- 直接比值，一个比“我”小，一个比“我”大，则“我”就是祖先。
- 都比我小，则递归到左子树中继续比较查找。
- 都比“我”大，则递归到右子树中继续比较查找。
情况二：如果为三叉链
- 类似于链表找交点问题
情况三：如果为普通二叉树
- 一个在“我”的左子树，一个在“我”的右子树，则“我”是祖先。
- 都在“我”的左子树，则递归到左子树中查找。
- 都在“我”的右子树，则递归到右子树中查找。
如果细分的话可以分为以上三种情况，但是本题就是一个普通二叉树，所以我们考虑第三种情况就可以了。
代码实现：
这道题的命名风格很重要，在判断p、q的位置时，分别定义了四个布尔值，命名清晰，读起来也很好理解。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
18
0- 0
已为社区贡献3条内容
所有评论(0)