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

发表于 | 分类于
字数统计: 288 | 阅读时长 ≈ 1

一、题目描述

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

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：

   1
    \
     3
    /
   2

输出：
1

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

提示：

二、题解

1.中序遍历+数组遍历

1.1 思路

  1. 使用中序遍历二叉搜索树，得到一个不严格的递增序列
  2. 遍历这个递增序列，找到最小差值

1.2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define maxSize 10000
int getMinimumDifference(struct TreeNode *root)
{
    int arr[maxSize];
    int arrTop = -1;
    struct TreeNode *stack[maxSize], *p = root;
    int stackTop = -1;
    while (stackTop != -1 || p != NULL)
    {
        while (p != NULL)
        {
            stack[++stackTop] = p;
            p = p->left;
        }
        p = stack[stackTop--];
        arr[++arrTop] = p->val;
        p = p->right;
    }
    int res = arr[1] - arr[0];
    for (int i = 2; i <= arrTop; i++)
    {
        int temp = arr[i] - arr[i - 1];
        res = res > temp ? temp : res;
    }
    return res;
}

既然和783题一样，那就顺便做了，嘿嘿嘿😄