代码随想录二刷 ｜二叉树 ｜ 二叉搜索树的最小绝对差

题目描述

530.二叉搜索树的最小绝对差

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：

提示：树中至少有 2 个节点。

解题思路 & 代码实现

题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。

遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。

递归法

在二叉搜素树中序遍历的过程中，我们就可以直接统治最小差值。我们需要用一个pre节点记录一下cur节点的前一个节点。

class Solution {
private:int result = INT_MAX;TreeNode* pre = NULL;void traversal(TreeNode* cur) {if (cur == NULL} return;traversal(cur->left);if (pre != NULL) {result = min(result, cur->val - pre->val);} pre = cur;traversal(cur->right);
public:int getMinimumDifference(TreeNode* root) {traversal(root);return result;}
};

迭代法

class Solution {
public:int getMinimumDifference() {stack<TreeNode> st;TreeNode* cur = root;TreeNode* pre = NULL:int result = INT_MAX;while (cur != NULL && !st.empty()) {if (cur != NULL) {st.push(cur);cur = cur->left;} else {cur = st.top();st.pop();if (pre != NULL) {result = min(result, cur->val - pre->val);}pre = cur;cur = cur->right;}}return result;}
};