问题Leetcode给定一棵二叉树，找到树中两个指定节点的最近公共祖先。百度百科对最近共同祖先的定义是：“对于有根树T的两个节点p和q，最近共同祖先表示为节点x，满足x是p和q的祖先，深度为x尽可能大（A节点也可以是它自己的祖先）。”示例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。因为根据定义，最近的共同祖先节点可以是节点本身。示例3：输入：root=[1,2],p=1,q=2输出：1提示：树中的节点数在[2,105]范围内。-109<=Node.val<=109所有Node.val都不同。p!=qp和q都存在于给定的二叉树中。思路DFS后序遍历分为四种情况：1.左右子树??均为空：左右子树都不包含p，q2。左子树为空：p和q都不在左子树中3.右子树为Empty：p,q不在右子树中4.左右子树??不为空：p,q在左子树中和右子树，当前根是最近的公共祖先节点代码Python3#二叉树节点的定义。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：deflowestCommonAncestor(self,root:'TreeNode',p:'TreeNode',q:'TreeNode')->'TreeNode':如果不是root或root==p或root==q:returnrootleft=self.lowestCommonAncestor(root.left,p,q)right=self.lowestCommonAncestor(root.right,p,q)#左子树和右子树如果不是左子树和右子树则为空：returnNone#右子树是emptyelifleftandnotright:returnleft#左子树为空elifnotleftandright:returnright#左右子树都不为空returnrootlinkGitHub
