530. 二叉搜索树的最小绝对值

一、题目描述

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

示例：

输入：

   1
    \
     3
    /
   2

输出：
1

解释：
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

提示：

• 树中至少有2个节点
• 本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同

二、思路

依然先放上LeetCode官方题解

1. 中序遍历

对搜索二叉树进行中序遍历，得到的结果是升序的，所以计算任意两个节点的差的绝对值的最小值，那么这两个节点在遍历结果中一定是挨着的。所以只需要计算比较遍历结果中所有相邻节点的值的差的最小值就好。对于遍历结果我们可以保存到一个数组中，然后开始计算。但是，在这里，直接在中序遍历过程中进行计算。

所以可以先创建一个变量pre来保存前一个节点的值，因为在遍历到第一个节点的时候，前边还没有节点，所以需要为pre赋初值。此题中二叉搜索树的节点都为非负值，所以可以为pre赋一个负值，下边代码中选择的是-1。

三、代码

1. 中序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

import sys
class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        res = sys.maxsize    # 为res赋一个系统最大值
        pre = -1
        queue = []
        while root or queue:
            while root:
                queue.append(root)
                root = root.left

            root = queue.pop()
            if pre != -1:
                res = min(abs(root.val-pre), res)
            pre = root.val
            root = root.right

        return res

四、表现

method	运行时间	表现	内存消耗	表现
1. 中序遍历	72ms	56.00%	15.5MB	33.47%