博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【leetcode】235. Lowest Common Ancestor of a Binary Search Tree
阅读量:5892 次
发布时间:2019-06-19

本文共 934 字,大约阅读时间需要 3 分钟。

题目如下:

解题思路:因为是BST,对于任意一个node,如果其val在p和q之间,那么说明p和q分别在其左子树和右子树,所以node就是其最低的祖父节点;如果val和q或者q相等,同样node就是其最低的祖父节点;如果p和q都比val大,说明这两个节点在node的右边,往右子树方向遍历;如果都小,往左子树方向遍历。

代码如下:

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def lowestCommonAncestor(self, root, p, q):        """        :type root: TreeNode        :type p: TreeNode        :type q: TreeNode        :rtype: TreeNode        """        minv,maxv = min(p.val,q.val),max(p.val,q.val)        if root.val == minv or root.val == maxv:            return root        elif root.val > minv and root.val < maxv:            return root        elif root.val < minv:            return self.lowestCommonAncestor(root.right, p, q)        else:            return self.lowestCommonAncestor(root.left, p, q)

 

转载于:https://www.cnblogs.com/seyjs/p/9640465.html

你可能感兴趣的文章
umount 时出现的 "Device is busy"问题
查看>>
Gulp+browser-sync打造前端开发自动刷新
查看>>
ASA-vlan-interface
查看>>
深度遍历搜索
查看>>
Weblogic8.X安装及连接池配置指南
查看>>
一看就懂的设计模式--设计模式分类
查看>>
Linux安装Maven
查看>>
document.createElement()的用法
查看>>
linux压缩命令(五)之tar总结
查看>>
MySQL 数据库怎样把一个表的数据插入到另一个表
查看>>
HTTP协议及其POST与GET操作差异 & C#中如何使用POST、GET等
查看>>
如何在Windows Server 2008R2上面批量添加AD用户及自定义OU批量添加用户
查看>>
集合框架总结
查看>>
Lync-Skype企业连通性部署解决方案
查看>>
限制user_agent
查看>>
ftp服务器高级配置
查看>>
【案例】关于weblogic性能问题的分析和解决方法
查看>>
使用adb devices命令无法识别夜神模拟器的解决方法
查看>>
rsync + inotify 实现主机间数据实时同步的原理
查看>>
Python--day5--常用模块
查看>>