每日一题时间:
2020-04-13
题目链接: 783. 二叉搜索树节点最小距离 官方题解链接: 二叉搜索树节点最小距离
给你一个二叉搜索树的根节点 root
,返回 树中任意两不同节点值之间的最小差值 。
示例 1:
输入:root = [4,2,6,1,3]
输出:1
示例 2:
输入:root = [1,0,48,null,null,12,49]
输出:1
提示:
[2, 100]
内0 <= Node.val <= 105
解题思路: 该题解法与 (Leetcode 2021 刷题计划) 173. 二叉搜索树迭代器 类似, 做题最关键的方法是举一反三
class Solution {
public:
int minDiffInBST(TreeNode* root) {
stack<TreeNode*> stk;
TreeNode *cur = root, *prev = root;
int res = INT_MAX;
while (cur != nullptr || !stk.empty()) {
while (cur != nullptr) {
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
stk.pop();
// 用来排除根节点无左节点从而产生最小值为 0 的情况
if (cur != prev) res = min(res, abs(cur->val - prev->val));
prev = cur;
cur = cur->right;
}
return res;
}
};
O(N)
O(N)
解题思路: 二叉搜索树如果遍历结果为单调递增, 因此采用递归方法进行最小值计算(当前值与上一个值的差的最小值)
class Solution {
public:
void dfs(TreeNode* root, int& pre, int& ans) {
if (root == nullptr) {
return;
}
dfs(root->left, pre, ans);
if (pre == -1) {
pre = root->val;
} else {
ans = min(ans, root->val - pre);
pre = root->val;
}
dfs(root->right, pre, ans);
}
int minDiffInBST(TreeNode* root) {
int ans = INT_MAX, pre = -1;
dfs(root, pre, ans);
return ans;
}
};
O(N)
O(N)
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。