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

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

Reference

https://www.programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

中序遍历,可以得到递增序列,求差值,最小绝对差值,相邻的元素差值最小。

遇到中序遍历求解的题目,需要用到上一个节点和当前节点比较,所以我们最好保存上一个节点,这样才方便于当前节点比较。

递归返回条件: node == nullpter;

零时保存的变量: preNode 上一个节点 maxDif最大差值

处理中间节点: 将当前节点与上一个节点的差值比较,如果大于maxDif则更新maxDif。

处理完毕中间节点，更新preNode。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    int res;
    TreeNode* pre;
    void traversal(TreeNode* node) {
        if (node == nullptr)
            return;
        traversal(node->left);
        cout << node->val << endl;
        if (pre != nullptr)
            res = std::min<int>(res, node->val - pre->val);
        pre = node;
        traversal(node->right);
    }
    int getMinimumDifference(TreeNode* root) {
        res = INT_MAX;
        traversal(root);
        return res;
    }
};