本文共 827 字，大约阅读时间需要 2 分钟。

一、问题描述

找出两个给定树节点的最低公共祖先（即最近公共祖先）。首先明确，什么是“祖先”？在树结构中，任一节点的祖先是该节点到根节点的所有后续节点。最近公共祖先则是两个节点所在路径的最后一个相同的节点。

二、解决方案

解决此问题，采用后序遍历方法。后续遍历可以帮助从左右子树中依次探索，逐渐缩小范围，找到最近的公共祖先。

解决思路：

代码实现：

Solution::lowestCommonAncestor(TreeNode* root, TreeNode* p,    TreeNode* q) {    if (root == NULL || root == p || root == q)        return root;    TreeNode* left = lowestCommonAncestor(root->left, p, q);    TreeNode* right = lowestCommonAncestor(root->right, p, q);    if (left == NULL)        return right;    if (right == NULL)        return left;    return root;}

三、运行结果

如图所示，代码逻辑正确，能够符合预期运行结果。

四、大佬解析

代码采用递归策略，通过后序遍历找到最近公共祖先。从根节点开始，若当前节点是p或q，直接返回。如果左、右子树找到符合条件的节点，则返回较低的那一侧。若两边同时找到，说明当前节点即为最近公共祖先。这种方法保证了在树结构中准确地找到两节点的最近相连点。

这个方案通过递归实现，保持了树的纯度，逻辑简单易懂。若对时间复杂度有要求，可能需优化，但本题递归实现可满足需求。代码注释清晰，易于理解，保证可维护性。

转载地址：http://jthhz.baihongyu.com/