Re: [閒聊] 每日LeetCode
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
推
02/17 08:38,
2年前
, 1F
02/17 08:38, 1F
→
02/17 08:39,
2年前
, 2F
02/17 08:39, 2F
晚安 寶
推
02/17 08:39,
2年前
, 3F
02/17 08:39, 3F
※ 編輯: idiont (140.113.229.216 臺灣), 02/17/2023 08:43:54
推
02/17 12:55,
2年前
, 4F
02/17 12:55, 4F
對耶 這樣寫起來好像更簡單了
※ 編輯: idiont (140.113.229.216 臺灣), 02/17/2023 13:27:17
討論串 (同標題文章)
完整討論串 (本文為第 236 之 719 篇)：