这道题的代码比较简单，看起来还挺容易看懂的，但是要把每一个细节都看懂到位就不太容易了。主要考虑如下：如何自底向上遍历？遍历整棵树还是部分树？如何将结果传递给根节点？这些问题需要弄清楚。如果直接看代码，可能想不到这些细节。.共同祖先问题还是比较难的，初学者还是需要慢慢消化！二叉树的最近共同祖先链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree给定一棵二叉树，找到两个指定节点的最近共同祖先在树上。百度百科对最近共同祖先的定义是：“对于有根树T的两个节点p和q，最近共同祖先表示为节点x，满足x是p和q的祖先，深度为x尽可能大（一个节点也可以是它自己的祖先）。”例如，给定以下二叉树：root=[3,5,1,6,2,0,8,null,null,7,4]二叉树的最近共同祖先示例1：输入：root=[3,5,1,6,2,0,8,null,null,7,4],p=5,q=1输出：3解释：最近的节点5和节点1的共同祖先是节点3。示例2：输入：root=[3,5,1,6,2,0,8,null,null,7,4],p=5,q=4输出：5解释：最近的节点5和节点4共同祖先是节点5。因为根据定义，最近的共同祖先节点可以是节点本身。解释：所有节点的值都是唯一的。p和q是不同的节点，都存在于给定的二叉树中。思路遇到这个问题，我首先想到的是能不能自底向上搜索，这样就可以找到共同的祖先。那么二叉树如何自下而上查找呢？回溯，二叉树回溯的过程是自下而上的。后序遍历是一个自然的回溯过程，必须先处理叶子节点。接下来我们看看如何判断一个节点是节点q和节点p的共同祖先。如果找到一个节点，节点p出现在左子树中，节点q出现在右子树中，或者节点q出现在左子树中，节点p出现在右子树中，那么这个节点就是节点p的最近共同祖先和问。使用后序遍历，回溯的过程是从低到高遍历节点。一旦找到具有这种条件的节点，它就是最近的公共节点。递归三部曲：确定递归函数的返回值和参数，要求递归函数的返回值告诉我们是否找到节点q或p，那么返回值为bool类型。但是我们仍然需要返回最近的公共节点。我们可以把上面题目中的返回值设为TreeNode*，那么如果遇到p或者q，就返回q或者p。如果返回值不为空，则表示我们找到了q或p。代码如下：TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q)判断终止条件如果找到节点p或q，或者遇到空节点，则返回。代码如下：if(root==q||root==p||root==NULL)returnroot;确定单层递归逻辑。值得注意的是，这道题中的函数是有返回值的，因为回溯的过程需要对递归函数的返回值进行判断，但是这道题中我们还是要遍历树的所有节点。我们在二叉树中说过：递归函数什么时候需要返回值，什么时候不需要返回值？据说递归函数如果有返回值，需要遍历某条边，但是如果有返回值，就要看如何处理返回值了！如果递归函数有返回值，如何区分是搜索一条边还是搜索整棵树？搜索一条边：if(递归函数(root->left))return；if(递归函数(root->right))return;搜索整个树写作：left=recursivefunction(root->left);right=递归函数(root->right);左右的逻辑处理；看到不同？在有返回值的递归函数的情况下：如果你想在搜索一条边时，当递归函数的返回值不为空时，立即返回。如果搜索整棵树，直接用一个变量left和right去抓返回值。左右顺序还是需要逻辑处理的，也就是中序遍历（也叫回溯）处理中间节点的逻辑。那么为什么要遍历整棵树呢？直觉上，找到最近的共同祖先一路回溯就够了。如图：二叉树的最近共同祖先如图直接返回7，多美啊。但实际上需要遍历根节点的右子树（即使此时已经找到目标节点），也就是图中的节点4、15、20。因为在下面代码的后序遍历中，如果要用left和right做逻辑处理，是不能马上返回的，只能等left和right逻辑处理完成后才能返回。left=递归函数（root->left）；right=递归函数（root->right）；左右的逻辑处理；所以这时候大家应该知道，我们要遍历整棵树。知道了这一点，我们对这个话题有了一定的深入了解。然后先用left和right分别抓取左子树和右子树的返回值，代码如下：TreeNode*left=lowestCommonAncestor(root->left,p,q);TreeNode*right=lowestCommonAncestor(root->右,p,q);如果left和right都不为空，说明此时root是距离最近的公共节点。这样比较容易理解。如果left为空，right不为空，则返回right，表示通过right返回目标节点，反之亦然。这里有同学不能理解为什么left为空，right不为空，通过right返回目标节点？如图：二叉树的最近公共祖先1中节点10的左子树返回null，右子树返回null目标值为7，那么节点10此时的处理逻辑就是返回右子树的返回值（最近的共同祖先7）！这一点也很重要。刷过这道题的同学可能不知道结果是怎样从底层传到头节点。那么如果left和right都为空，则可以返回left或right，即返回空。代码如下：if(left==NULL&&right!=NULL)returnright;elseif(left!=NULL&&right==NULL)returnleft;else{//(left==NULL&&right==NULL)returnNULL;}然后寻找最小共同祖先，完整流程图如下：最近共同祖先二叉树的2从图中可以看出我们是如何回溯整个二叉树并将结果返回给头节点的！整体代码如下：TreeNode*left=lowestCommonAncestor(root->left,p,q);TreeNode*right=lowestCommonAncestor(root->right,p,q);if(left!=NULL&&right!=NULL)returnroot;if(left==NULL&&right!=NULL)returnright;elseif(left!=NULL&&right==NULL)returnleft;else{//(left==NULL&&right==NULL)returnNULL;}}};稍微简化一下，代码如下：root;TreeNode*left=lowestCommonAncestor(root->left,p,q);TreeNode*right=lowestCommonAncestor(root->right,p,q);if(left!=NULL&&right!=NULL)returnroot;if(left==NULL)returnright;returnleft;}};综上所述，刷过这道题的同学可能不太了解回溯的过程，以及结果是如何层层传递的。那么我给大家总结如下三点：求最小共同祖先，需要自底向上遍历，所以二叉树只能通过后序遍历（即：回溯）从低到高遍历.在回溯的过程中，必须遍历整棵二叉树。即使找到了结果，也必须遍历其他节点，因为递归函数的返回值（也就是代码中的左右）必须要进行逻辑判断。需要理解为什么返回值left为空right不为空返回right，为什么返回的right可以用来传递结果给上层。可以说这里的每一步都是有难度的，需要对二叉树、递归和回溯有一定的了解。这道题没有给出迭代的方法，因为迭代的方法不适合模拟回溯的过程。了解递归解决方案就足够了。其他语言版本JavaclassSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){returnlowestCommonAncestor1(root,p,q);}publicTreeNodelowestCommonAncestor1(TreeNoderoot,TreeNodep,TreeNodeq){if(root==空||root==p||root==q){returnroot;}TreeNodeleft=lowestCommonAncestor1(root.left,p,q);TreeNoderight=lowestCommonAncestor1(root.right,p,q);if(left!=null&&right!=null){//分别找到了左右子树，说明此时的根就是要求的结果returnroot;}if(left==null){returnright;}returnleft;}}//代码精简版classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(root==null||root.val==p.val||root.val==q.val)returnroot;TreeNodeleft=lowestCommonAncestor(root.left,p,q);TreeNoderight=lowestCommonAncestor(root.right,p,q);if(left!=null&&right!=null)returnroot;elseif（左==null&&右!=null)返回权；elseif(left!=null&&rightt==null)returnleft;elsereturnnull;}}Python//recursiveclassSolution:deflowestCommonAncestor(self,root:'TreeNode',p:'TreeNode',q:'TreeNode')->'TreeNode':ifnotrootorroot==porroot==q:returnroot//foundnodeporq,orencounteredanemptynodeleft=self.lowestCommonAncestor(root.left,p,q)//leftright=self.lowestCommonAncestor(root.right,p,q)//rightifleftandright:returnroot//middle:left和right不为空，root是最近的公共节点elifleftandnotright:returnleft//目标节点是elifnotleftandrightreturnedbyleft:returnright//目标节点由right返回else:returnNone//没有找到
