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

17750
来自专栏WindCoder

数据统计第一弹-按时/天/周/月补全某一段时间的数据-Java核心逻辑

本代码均结合之前的发布的DateUtil使用,之后的mysql查询部分看心情发布,就这么任性~ ~

14610
来自专栏书山有路勤为径

二叉树-最近的公共祖先

已知二叉树,求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u,满足在树上最低(离根最 远),且v,w两个节点都是u的子孙。...

15020
来自专栏拂晓风起

java LinkedList ArrayList 随机访问效率 list.get(int index)

11150
来自专栏数据结构与算法

Day2平衡树笔记

线段树不支持的操作:删除,插入 ---- 常见的平衡树 treap 慢||好写 sbt(大小平衡的树) 非常快 比较好写 ||功能不全 rbt 红黑树 特...

32660
来自专栏猿人谷

双向链表

双向链表       在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表...

27650
来自专栏工科狗和生物喵

【我的漫漫跨考路】数据结构之单链表线性存储实现 Beta

正文之前 ? 昨天晚上阶段性的完成了一部分数学的复习,所以今天打算撸一撸代码,然后发现提电脑忘指针。所以自己磕磕盼盼,对照了一下网上的代码,总算把线性存储单链表...

371110
来自专栏尾尾部落

[剑指offer] 按之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

9520
来自专栏技术小黑屋

Java性能调优之容器扩容问题

在Java和Android编程中,我们经常使用类似ArrayList,HashMap等这些容器。这些容器少则存储几条,多则上千甚至更多。作为性能调优的一部分,容...

12110
来自专栏swag code

Calendar类-set()方法的延时操作

set(f,value)方法将日历字段f更改为value,此外还设置了一个内部成员变量,

7820

扫码关注云+社区

领取腾讯云代金券