【LeetCode题解】530_二分搜索树的最小绝对值差
描述
给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。
示例 :
输入：
1
\
3
/
2
输出：
1
解释：
最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
注意： 树中至少有2个节点。
方法一、中序遍历二分搜索树
思路
中序遍历二分搜索树，计算当前节点数据与上一个节点数据的绝对值的差值，遍历结束返回最小的绝对值差值。
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int minDiff = Integer.MAX_VALUE;
TreeNode prev = null;
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
if (prev != null) {
minDiff = Math.min(minDiff, root.val - prev.val);
}
prev = root;
inOrder(root.right);
}
public int getMinimumDifference(TreeNode root) {
inOrder(root);
return minDiff;
}
}
// Runtime: 8 ms
// Your runtime beats 99.91 % of java submissions.
复杂度分析：
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(1)\)
Python 代码
# 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):
"""
:type root: TreeNode
:rtype: int
"""
l = list()
def in_order(root):
if root:
in_order(root.left)
l.append(root.val)
in_order(root.right)
in_order(root)
return min([b - a for a, b in zip(l, l[1:])])
# Runtime: 72 ms
# Your runtime beats 86.68 % of python3 submissions.
复杂度分析：
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)