求两个节点最近的祖先节点,思路是找到根节点到所求节点的路径,那么两条路径分叉处就是祖先节点 递归,假定root不是p,也是不是q,不然root就为所求
class Solution(object): def findpq(self, root, p, q): if not root or(self.pathP and self.pathQ): return if root == p: self.pathP = self.mycopy(self.path) if root == q: self.pathQ = self.mycopy(self.path) if root.left: # 将左子树加入路径 self.path.append(root.left) self.findpq(root.left, p, q) # 左子树返回时,将左子树抛出 self.path.pop() if root.right: self.path.append(root.right) self.findpq(root.right, p ,q) self.path.pop() def mycopy(self,path): pathcopy = [] for el in path: pathcopy.append(el) return pathcopy def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if root ==p or root == q: return root self.pathP = None self.pathQ = None self.path = [] self.findpq(root, p, q) #print self.path i = 0 flag = 0 minpathLen = min(len(self.pathP), len(self.pathQ)) for i in range(minpathLen): if self.pathP[i] != self.pathQ[i]: flag = 1 break # 确定路径长度为i if i == 0 and flag==1: return root #print self.pathP if flag == 0: return self.pathP[i] '''else说明终止循环是因为有不同路径''' else: return self.pathP[i-1]
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句