题目描述

设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。

算法

第一版的思路来源：将树的节点按照一定规则编号，然后反向计算祖节点的位置

class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:def look(r,n):if r:self.d1[r]=nself.d2[n]=rlook(r.left,2*n+1)look(r.right,2*n+2)self.d1={}self.d2={}look(root,0)p,q=self.d1[p],self.d1[q]while p!=q:if p>q:p,q=q,pif q%2:q=(q-1)//2else:q=(q-2)//2return self.d2[p]

class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:def look(r,n):if r and self.k:self.d1[r]=nself.d2[n]=rif r==self.p:self.k-=1self.p=nelif r==self.q:self.k-=1self.q=nlook(r.left,2*n+1)look(r.right,2*n+2)self.d1={}self.d2={}self.p,self.q=p,qself.k=2look(root,0)p,q=self.p,self.qwhile p!=q:if p>q:p,q=q,pif q%2:q=(q-1)//2else:q=(q-2)//2return self.d2[p]

递归

优秀的思路：

class Solution:def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:# 如果当前节点为空，就返回空if not root:return None# 如果当前结点就是p或者q，就返回当前节点if root in [p, q]:return root# 分别去左右子树里面去找left = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)# 如果左右子树里各有一个p或者q，那么当前就是最前结点if left and right:return root# 如果都在左边，那就是当前这个左边的elif left:return left# 要么就是右边的elif right:return rightreturn None