专栏首页数据处理236. Lowest Common Ancestor of a Binary Tree

236. Lowest Common Ancestor of a Binary Tree

求两个节点最近的祖先节点,思路是找到根节点到所求节点的路径,那么两条路径分叉处就是祖先节点 递归,假定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]   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 236. Lowest Common Ancestor of a Binary Tree

    用户1733462
  • 随机梯度下降(Stochastic gradient descent)和 批量梯度下降(Batch gradient descent )

    用户1733462
  • 回归

    看一下损失函数的导函数tanh(x),当x偏离0时,tanh(x)趋向+1或者-1

    用户1733462
  • 236. Lowest Common Ancestor of a Binary Tree

    用户1733462
  • 基础积累 | 图像分割损失函数最全面、最详细总结,含代码

    论文地址:https://arxiv.org/pdf/2006.14822.pdf

    AI算法修炼营
  • 一文看尽15种语义分割损失函数(含代码解析)

    https://github.com/shruti-jadon/Semantic-Segmentation-Loss-Functions

    Amusi
  • python+pygame游戏开发之使用Py2exe打包游戏

    最近在用python+pygame 开发游戏,写完以后在分享给朋友玩的时候遇到了很大的问题,只有搭建了环境才能运行python脚本。

    马三小伙儿
  • 基于计算机视觉和OpenCV:创建一个能够计算道路交通流量的应用

    本文将介绍如何在不需要大量的深度学习算法的情况下,基于计算机视觉来计算道路交通流量。本教程只使用Python和OpenCV,在背景差分算法的帮助下,实现非常简单...

    AiTechYun
  • 微信小程序-云开发 数据库http接口封装

    最近学习一下微信小程序的云开发,作为serverless架构,着实省去很多麻烦,省的搞https证书了,也不用写api,但是总是要建后台系统的,云开发的数据库是...

    纷扰D梦
  • (二)中文文本分类--机器学习算法原理与编程实践 - 简书

    本章知识点:中文分词,向量空间模型,TF-IDF方法,文本分类算法和评价指标 使用的算法:朴素的贝叶斯算法,KNN最近邻算法 python库:jieba分词,S...

    会呼吸的Coder

扫码关注云+社区

领取腾讯云代金券