## 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

``````

## 思路

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

https://my.oschina.net/wonz/blog/4916964