leetcode 530. Minimum Absolute Difference in 二叉搜索树的中序遍历 + 深度优先遍历DFS

痛定思痛。 2022-06-03 03:27 144阅读 0赞

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

Input:

1
        \
         3
        /
       2

Output:  
1

Explanation:  
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).  
Note: There are at least two nodes in this BST.

题意很简单就是一个简单的DFS深度优先遍历，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    
    /*
    struct TreeNode
    {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    
    class Solution
    {
    public:
        int getMinimumDifference(TreeNode* root)
        {
            vector<int> res;
            dfs(root, res);
    
            int minDif = INT_MAX;
            for (int i = 1; i < res.size(); i++)
                minDif = min(minDif, res[i] - res[i - 1]);
            return minDif;
        }
    
        void dfs(TreeNode* root, vector<int>& res)
        {
            if (root == NULL)
                return;
            else
            {
                dfs(root->left, res);
                res.push_back(root->val);
                dfs(root->right, res);
            }
        }
    };