二叉搜索树的最小绝对差

Category	Difficulty	Likes	Dislikes
algorithms	Easy (55.49%)	99	-

Tags

tree

Companies

google

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

示例：

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

   1
    \
     3
    /
   2

输出：
1

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

提示：

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

Discussion | Solution

解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int last = INT_MAX, minm = INT_MAX;
        recur(root, last, minm);
        return minm;
    }

    void recur(TreeNode* root, int& last, int& minm) {
        if (!root) return;

        recur(root->left, last, minm);

        auto a = abs(root->val-last);
        if ( a < minm) {
            minm = a;
        }
        last = root->val;

        recur(root->right, last, minm);
    }
};

二叉搜索树的最小绝对差

二叉搜索树的最小绝对差

解法

相关文章：