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 条评论
登录 后参与评论

相关文章

来自专栏WindCoder

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

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

14610
来自专栏尾尾部落

[剑指offer] 二叉树的下一个结点

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

8510
来自专栏拂晓风起

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

11150
来自专栏小狼的世界

Aptana的破解

最近写JS比较多,常常苦恼与没有一个顺手的IDE。Editplus虽然用的熟,不过那个的效率太低而且代码看起来也很不方便,经过一个多月的试用,发现了一款好用的编...

10520
来自专栏趣学算法

数据结构 第13讲 三元组 (F、C、L/R) 序列创建二叉树

/* 输入三元组 (F、C、L/R) 序列输入一棵二叉树的诸边(其中 F 表示双亲结点的标识,C 表示孩子结点标识,L/R...

32030
来自专栏机器学习与自然语言处理

03-树2. List Leaves (25) 二叉树的层序遍历

03-树2. List Leaves (25) 题目来源:http://www.patest.cn/contests/mooc-ds/03-%E6%A0%912...

27590
来自专栏猿人谷

双向链表

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

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

Day2平衡树笔记

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

32660
来自专栏项勇

笔记26 | 总结Android的获取系统时间的几种方法

20250
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

15810

扫码关注云+社区

领取腾讯云代金券