leetcode-530. 二叉搜索树的最小绝对差刷题笔记（c++）

Bertha 。 2023-02-23 07:52 19阅读 0赞

#### 写在前面 ####

*  难度：简单
 *  一时间没想起来，，，

#### 题目详情 ####

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
    
    示例：
    
    输入：
    
       1
        \
         3
        /
       2
    
    输出：
    1
    
    解释：
    最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
     
    
    提示：
    
    树中至少有 2 个节点。
    本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同

#### ac代码 ####

*  解题思路
    
     *  中序遍历，结果数组有序
     *  迭代计算数组相邻元素差值，取最小值

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution
    {
        
    public:
        vector<int> pv;
        void inOrder(TreeNode* root)
        {
        
            if(!root)
                return;
            inOrder(root->left);
            pv.push_back(root->val);
            inOrder(root->right);
        }
        int getMinimumDifference(TreeNode* root)
        {
        
            int mins = 999999999 ;
            inOrder(root);
            for(int i=0; i<pv.size()-1; i++)
                mins = min(pv[i+1]-pv[i], mins);
            return mins;
        }
    };

*  参考文章
    
     *  [530. 二叉搜索树的最小绝对差][530.]
     *  [LeetCode 530. 二叉搜索树的最小绝对差（中序遍历）][LeetCode 530.]
        
         *  堆栈法，供参考，不再搬运，，，

[530.]: https://www.cnblogs.com/8013-cmf/p/13164295.html
[LeetCode 530.]: https://blog.csdn.net/qq_21201267/article/details/102964835