Leetcode 530 - Minimum Absolute Difference in BST

題目

Problem#

給你一個二元搜尋樹(Binary Search Tree, BST)，問你樹上所有點相差最小的是多少？

測資限制#

• $2 \le n \le 10^4$
• $0 \le val \le 10^5$

想法#

要找到所有點數值相差最小，首先就是要把樹遍歷過，把所有點蒐集在 array 中 $O(n)$
接著找數值相差最小，當然可以直接暴力找 $O(n^2)$，但是因為要找的是相差最小，而如果把陣列由小排到大，則對於 $i$ ，和它相差最小只會是 $i-1$ 或 $i+1$ ($0 \le i \le n-1$)
所以就可以直接掃一遍，相鄰的數字相減找最小即可 $O(n)$。

但別忘記了還要把陣列從小排到大，可以直接用 std::sort $O(n\log{n})$，或是在遍歷整顆樹的時候，用中序(In-Order)的方式遍歷，蒐集好的 array 會是已經排好序的，因為 bst 的性質： $O(n)$。

• 空間複雜度: $\mathcal{O}(n)$

AC Code#

Copy

class Solution {
public:
    int getMinimumDifference(TreeNode* r)
    {
        vector<int> v;
        stack<TreeNode*> s({r});
        int ans = INT_MAX;
 
        while(!s.empty())
        {
            auto p = s.top(); s.pop();
            v.push_back(p->val);
            if(p->left) s.push(p->left);
            if(p->right) s.push(p->right);
        }
 
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size()-1; i++)
        {
            ans = min(ans, abs(v[i]-v[i+1]));
        }
        return ans;
    }
};

view raw leetcode/530.cpp delivered with ❤ by emgithub

Copy

class Solution2 {
public:
    vector<int> v;
    void dfs(TreeNode* p)
    {
        if(p->left) dfs(p->left);
        v.push_back(p->val);
        if(p->right) dfs(p->right);
    }
    int getMinimumDifference(TreeNode* r)
    {
        int ans = INT_MAX;
        dfs(r);
        for(int i = 0; i < v.size()-1; i++)
            ans = min(ans, abs(v[i]-v[i+1]));
        return ans;
    }
};

view raw leetcode/530.cpp delivered with ❤ by emgithub

賞析#

官方題解：也可以不用蒐集成一個 array，而是記住上個訪問的 node，如此在中序遍歷仍可以算用前後相減找最小。

心得#

一開始以為這種有 struct TreeNode 題目都不讓你裝成 array，結果官方題解就寫了這種方法XDD