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

问题地址

LeetCode每日一题/2020-10-12

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

问题描述

规则

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

示例

• 示例1

输入：
   1
    \
     3
    /
   2
输出：1

解释

最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

提示：

• 树中至少有 2 个节点。
• 本题与 783 相同

解析

解题思路

• 我们都知道二叉搜索树左子树不大于根节点，右子树不小于根节点。我们采用中序遍历的处理这个问题；
• 方法一：先利用一次中序遍历将值保存在一个数组中再进行遍历求解；
• 方法二：在中序遍历的过程中用一个变量保存前驱节点的值，这样即能边遍历边更新答案，不再需要显式创建数组来保存，该变量的初始值需设置为任意负数标记开头。

数据操作分析

复杂度分析

1. 时间复杂度
2. 空间复杂度

编码实现

public class LeetCode0530_MinimumAbsoluteDifferenceInBst {
    int ans = Integer.MAX_VALUE;
    int preVal = -1;
    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;
        if (root.left != null) {
            dfs(root.left);
        }
        if (preVal == -1) {
            preVal = root.val;
        } else {
            ans = Math.min(root.val-preVal, preVal);
            preVal = root.val;
        }
        if (root.right!=null) dfs(root.right);
    }
}

官方解法

前言

• 本题是经典的NP 完全问题，也就是说，如果你发现了该问题的一个多项式算法，那么恭喜你证明出了 P=NP，可以期待一下图灵奖了。
• 正因如此，我们不应期望该问题有多项式时间复杂度的解法。我们能想到，例如基于贪心算法的「将数组降序排序后，依次将每个元素添加至当前元素和较小的子集中」之类的方法都是错误的，可以轻松地举出反例。因此，我们必须尝试非多项式时间复杂度的算法，例如时间复杂度与元素大小相关的动态规划。

方法一：中序遍历

思路与算法：

• 考虑对升序数组 a 求任意两个元素之差的绝对值的最小值，答案一定为相邻两个元素之差的最小值
  
  • 其中 n 为数组 a 的长度。其他任意间隔距离大于等于 2 的下标对 (i,j) 的元素之差一定大于下标对 (i,i+1) 的元素之差，故不需要再被考虑。
• 回到本题，本题要求二叉搜索树任意两节点差的绝对值的最小值，而我们知道二叉搜索树有个性质为二叉搜索树中序遍历得到的值序列是递增有序的，因此我们只要得到中序遍历后的值序列即能用上文提及的方法来解决。
• 朴素的方法是经过一次中序遍历将值保存在一个数组中再进行遍历求解，我们也可以在中序遍历的过程中用 pre 变量保存前驱节点的值，这样即能边遍历边更新答案，不再需要显式创建数组来保存，需要注意的是 pre 的初始值需要设置成任意负数标记开头，下文代码中设置为 −1。
• 二叉树的中序遍历有多种方式，包括递归、栈、Morris 遍历等，读者可选择自己最擅长的来实现。下文代码提供最普遍的递归方法来实现，其他遍历方法的介绍可以详细看「94. 二叉树的中序遍历」的题解，这里不再赘述。

复杂度分析：

1. 时间复杂度:O(n)，其中 n 为二叉搜索树节点的个数。每个节点在中序遍历中都会被访问一次且只会被访问一次，因此总时间复杂度为 O(n)。

2. 空间复杂度：O(n)。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 O(n) 级别。

编码实现

class Solution {
    int pre;
    int ans;

    public int getMinimumDifference(TreeNode root) {
        ans = Integer.MAX_VALUE;
        pre = -1;
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (pre == -1) {
            pre = root.val;
        } else {
            ans = Math.min(ans, root.val - pre);
            pre = root.val;
        }
        dfs(root.right);
    }
}

精彩评论

跳转地址1：530. 二叉搜索树的最小绝对差:【有序数组】详解

思路

• 题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。
• 注意是二叉搜索树, 二叉搜索树可是有序的。
• 遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。

递归

• 那么二叉搜索树如果采用中序遍历，其实就是一个有序数组。
• 在一个有序数组上求两个数最小差值，这是不是就是一道送分题了。
• 最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了

编码实现

class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {
    if (root == NULL) return;
    traversal(root->left);
    vec.push_back(root->val); // 将二叉搜索树转换为有序数组 
    traversal(root->right);
}
public:
    int getMinimumDifference(TreeNode* root) {
        vec.clear();
        traversal(root);
        if (vec.size() < 2) return 0;
        int result = INT_MAX;
        for (int i = 1; i < vec.size(); i++) { // 统计有序数组的最小差值
            result = min(result, vec[i] - vec[i-1]);
        }
        return result;
    }
};

• 以上代码是把二叉搜索树转化为有序数组了，其实在二叉搜素树中序遍历的过程中，我们就可以直接计算了。需要用一个pre节点记录一下，当前节点的前一个节点。
  

改进后编码实现

class Solution {
private:
int result = INT_MAX;
TreeNode* pre;
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(TreeNode* root) {
        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;
    }
};