LeetCode | 0530. 二叉搜索树的最小绝对差【Python】

Wonz 2021-01-20 22:45:16
Python github def


Problem

LeetCode

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:
1
\
3
/
2
Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note:

问题

力扣

给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。

示例:

输入:
1
\
3
/
2
输出:
1
解释:
最小绝对差为 1,其中 2  1 的差的绝对值为 1(或者 2  3)。

提示:

思路

DFS

法一:dfs遍历取节点值,再单独计算最小绝对差
法二:dfs遍历直接进行绝对值比较

Python3 代码

法一

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getMinimumDifference(self, root: TreeNode) -> int:
# solution one: dfs遍历取节点值,再单独计算最小绝对差
def dfs(root):
if not root:
return
# 中序遍历是递增的
if root.left:
dfs(root.left)
tmp_val.append(root.val)
if root.right:
dfs(root.right)
tmp_val = []
dfs(root)
res = float("inf")
for i in range(len(tmp_val) - 1):
res = min(res, abs(tmp_val[i] - tmp_val[i + 1]))
return res

法二

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getMinimumDifference(self, root: TreeNode) -> int:
# solution two: dfs遍历直接进行绝对值比较
pre = -1
res = float("inf")
def dfs(root):
nonlocal pre, res
if not root:
return
# 中序遍历是递增的
if root.left:
dfs(root.left)
if pre != -1:
res = min(res, abs(pre - root.val))
pre = root.val
if root.right:
dfs(root.right)
dfs(root)
return res

GitHub 链接

Python

版权声明
本文为[Wonz]所创,转载请带上原文链接,感谢
https://my.oschina.net/wonz/blog/4916964

  1. 【七天搞定Python】day01.Python环境配置、pip、IDE、注释、变量,数据类型、标识符/关键字、输出、输入
  2. Life is short, I learn Python
  3. Python image enhancement and special effects - using Baidu AI to color black and white images
  4. Python environment configuration, Pip, IDE, comment, variable, data type, identifier / keyword, output, input
  5. 为什么说Python是最伟大的语言?看图就知道了 - 知乎
  6. Why is Python the greatest language? Just look at the picture. - Zhihu
  7. 通过创建视频游戏来学习 Python
  8. Learn Python by creating video games
  9. Python3版本下创建计算给定日期范围内工作日方法
  10. Creating a method to calculate working days within a given date range in Python 3
  11. 图解爬虫,用几个最简单的例子带你入门Python爬虫
  12. Graphical crawler, with a few of the simplest examples to take you to the introduction of Python crawler
  13. python+requests基础知识
  14. Basic knowledge of Python + requests
  15. python自定义windowsr日志支持文件分割
  16. python+requests基础知识
  17. Python custom Windowsr log supports file segmentation
  18. Basic knowledge of Python + requests
  19. 高级测试 | Python笔试题
  20. 火了!开源的 Python 抢票神器,过年回家就看这一波了!
  21. Python 爬虫进阶 - 前后端分离有什么了不起,过程超详细!
  22. 【python】使用pip提示ModuleNotFoundError
  23. 【python】虚拟环境搭建
  24. Advanced test | Python written test questions
  25. Fire! Open source Python ticket grabbing artifact, come home to see this wave of New Year!
  26. Python crawler advanced - before and after the end of the separation of what great, super detailed process!
  27. [Python] prompt modulenotfounderror with PIP
  28. Building a virtual environment
  29. Serverless 架构下用 Python 轻松搞定图像分类和预测
  30. Easy image classification and prediction with Python under serverless architecture
  31. python协程爬取某网站的老赖数据
  32. Python coroutine crawls Laolai data of a website
  33. 使用Python分析姿态估计数据集COCO的教程
  34. Using Python to analyze the data set coco of attitude estimation
  35. win环境 python3 flask 上手整理 环境搭建(一)
  36. Getting started with win environment python3 flash
  37. Python实现一个论文下载器,赶紧收藏
  38. win环境 python3 flask 上手整理 快速上手-基础操作(二)
  39. Python 中常见的配置文件写法
  40. Python to achieve a paper Downloader, quickly collect
  41. Python批量 png转ico
  42. 使用line_profiler对python代码性能进行评估优化
  43. 使用line_profiler对python代码性能进行评估优化
  44. Getting started with Python 3 flash in win environment
  45. Common ways to write configuration files in Python
  46. Python会在2021年死去吗? Python 3.9最终版本的回顾
  47. Python batch PNG to ICO
  48. Using line_ Profiler evaluates and optimizes the performance of Python code
  49. Using line_ Profiler evaluates and optimizes the performance of Python code
  50. Will Python die in 2021? A review of the final version of Python 3.9
  51. Python3 SMTP send mail
  52. Understanding closures in Python: getting started with closures
  53. Python日志实践
  54. Python logging practice
  55. [python opencv 计算机视觉零基础到实战] 十、图片效果毛玻璃
  56. [python opencv 计算机视觉零基础到实战] 九、模糊
  57. 10. Picture effect ground glass
  58. [Python opencv computer vision zero basis to actual combat] 9. Fuzzy
  59. 使用line_profiler對python程式碼效能進行評估優化
  60. Using line_ Profiler to evaluate and optimize the performance of Python code