Re: [閒聊] 每日LeetCode

[idiont (supertroller)]

783. Minimum Distance Between BST Node

給一棵二元搜尋樹，
求任意兩節點差值的最小值。


Example 1:

Input: root = [4, 2, 6, 1, 3]
Output: 1

Explanation:
https://assets.leetcode.com/uploads/2021/02/05/bst1.jpg
[2, 1], [2, 3], [4, 3] 差值都是 1


Example 2:

Input: root = [1, 0, 48, null, null, 12, 49]
Output: 1

Explanation:
https://assets.leetcode.com/uploads/2021/02/05/bst2.jpg
[1, 0], [48, 49] 差值皆為 1



解題思路:

給定的是一顆二元搜尋樹，
最接近當前節點的值會是左子樹的最大值以及右子樹的最小值，
找到後進行計算看看哪個比較小，
對所有子樹都做過一次就能找到答案，
但要避免重複走訪會增加時間複雜度。


C++ code:

class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int ans = INT_MAX;
        recursive(root, ans);
        return ans;
    }

    pair<int, int> recursive(TreeNode* root, int &ans){
        if(!root) return {0, 0};
        auto [lmin, lmax] = recursive(root->left, ans);
        auto [rmin, rmax] = recursive(root->right, ans);
        if(root->left) ans = min(ans, abs(root->val - lmax));
        if(root->right) ans = min(ans, abs(root->val - rmin));
        return {root->left ? lmin : root->val, root->right ? rmax :
root->val};
    }
};

---

另一種解法:
對樹做中序遍歷可以得到一個排序過的陣列，
把它存起來然後檢查兩兩相鄰值的差值就好。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676594242.A.C97.html
推 a9486l: 大師
→ a9486l: 回去睡覺了
晚安 寶
推 greenertea: 大師
※ 編輯: idiont (140.113.229.216 臺灣), 02/17/2023 08:43:54
推 NTHUlagka: 第二種解法可以用一個數字紀錄中序前一個數字即可
對耶 這樣寫起來好像更簡單了
※ 編輯: idiont (140.113.229.216 臺灣), 02/17/2023 13:27:17