问题Leetcode设计并实现了一个算法，用于查找二叉树中两个节点的第一个公共祖先。其他节点不得存储在单独的数据结构中。注意：这不一定是二叉搜索树。例如，给定以下二叉树：root=[3,5,1,6,2,0,8,null,null,7,4]3/\51/\/\6208/\74示例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是不同的节点，都存在于给定的二叉树中。思路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)#左右子树都为空ifnotleftandnotright:returnNone#右子树为空elifleftandnotright:returnleft#左子树为空elifnotleftandright:returnright#左右子树都为空else:returnroot链接到GitHub
