Leetcode | 0530. Minimum absolute difference of binary search tree [Python]

Wonz 2021-01-20 22:45:33
leetcode minimum absolute difference binary

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:

problem

Power button

Give you a binary search tree with nonnegative nodes , Please calculate the minimum absolute value of the difference between any two nodes in the tree .

Example ：

Input ：
1
\
3
/
2
Output ：
1
explain ：
The minimum absolute difference is  1, among  2  and  1  The absolute value of the difference is  1（ perhaps  2  and  3）.

Tips ：

Ideas

DFS

Law 1 ：dfs Traverse to get node value , Then calculate the minimum absolute difference separately
Law two ：dfs Traversal makes absolute value comparison directly

Python3 Code

Law 1

# 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 Traverse to get node value , Then calculate the minimum absolute difference separately
def dfs(root):
if not root:
return
# Middle order traversal is incremental
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

Law two

# 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 Traversal makes absolute value comparison directly
pre = -1
res = float("inf")
def dfs(root):
nonlocal pre, res
if not root:
return
# Middle order traversal is incremental
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