【力扣-二叉树】17二叉搜索树的最小绝对差 530 二叉

发表于

「这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」

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

题目描述

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

1
2
ini复制代码输入： root = [4,2,6,1,3]
输出： 1

示例 2：

1
2
csharp复制代码输入： root = [1,0,48,null,null,12,49]
输出： 1

递归法

遇到在二叉搜索树上求最值，求差值之类的问题，都要考虑到二叉搜索树有序的，要充分利用好这一特点。利用中序遍历可以得到一个有序的递增数组，在通过数组来获得想要的值

  • 递归法1 : 中序递归遍历，使用数组存储每个节点的值。遍历数组，相邻的两个数作差，得到差值的最小值。
  • 递归法2 : 中序递归遍历，使用 pre 指针，指向当前遍历结点的前一个结点，在遍历的过程中计算最小差值。

递归法1

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
35
36
37
38
39
40
41
c++复制代码#define MAX_INT 65536

class Solution
{
public:
    int getMinimumDifference(TreeNode *root)
    {
        // 清空数组
        vec.clear();
        // 中序遍历，将节点的值加入到数组中
        traversal(root);
        int minDiff = MAX_INT;
        // 遍历数组，求出最小的差值
        for (int i = 1; i < vec.size(); i++)
        {
            if (vec[i] - vec[i - 1] < minDiff)
            {
                minDiff = vec[i] - vec[i - 1];
            }
        }
        return minDiff;
    }

private:
    // 定义全局数组，用来存储每个节点的值
    vector<int> vec;
    // 中序遍历数组
    void traversal(TreeNode *node)
    {
        if (node == NULL)
        {
            return;
        }
        // 左
        traversal(node->left);
        // 中
        vec.push_back(node->val);
        // 右
        traversal(node->right);
    }
};

递归法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
35
36
c++复制代码#define MAX_INT 65536

class Solution
{
private:
    // 记录最小的差值
    int result = MAX_INT;

    // 记录遍历结点的前一个结点
    TreeNode *pre;
    void traversal(TreeNode *cur)
    {
        if (cur == NULL)
        {
            return;
        }
        // 左
        traversal(cur->left);
        // 中
        if (pre != NULL)
        {
            result = min(result, cur->val - pre->val);
        }
        // 记录前一个结点
        pre = cur;
        // 右
        traversal(cur->right);
    }

public:
    int getMinimumDifference(TreeNode *root)
    {
        traversal(root);
        return result;
    }
};

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%