Leetcode-530-二叉搜索树的最小绝对值

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

题目描述：

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

示例：

输入：

   1
    \
     3
    /
   2

输出：
1

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

提示：

• 树中至少有 2 个节点。

思路 :中序遍历

• 看到二叉搜索树，就能想到中序遍历。
• 遍历一个二叉树，会访问每一个节点，拿节点做一些事情。
• 而中序遍历，它对于每一个节点，都先访问处理它的左子树中的节点，再访问处理它本身，再访问处理它的右子树中的节点。

• 由于二叉搜索树的性质，中序遍历访问处理的节点值的大小是递增的。
• 题目要求任意两个节点的最小的差值，它肯定发生在递增排列后，相邻的节点值之间。

优化 ： 我们用一个变量，保存上一个访问处理的节点值，求出当前访问的节点值与它之差，挑战最小的纪录，更小就更新。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int pre;
    int ans;

    public int getMinimumDifference(TreeNode root) {
        ans = Integer.MAX_VALUE;
        pre = -1; //pre 用于保存前一个root.val
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode root){
        // 1. 递归结束的条件
        if(root == null){
            return;
        }

        // 2. 中序遍历
        dfs(root.left);
        // 处理逻辑
        if(pre == -1){
            pre = root.val;
        }else{
            ans = Math.min(ans,root.val - pre);
            pre = root.val; // pre更新为当前节点的值
        }
        dfs(root.right);
    }
}

复杂度分析

• 时间复杂度 ： O(n) 其中n是二叉搜索树节点的个数。每个节点在中序遍历中只会被访问一次。因此总的时间复杂度是O(n)
• 空间复杂度 ： O(n) 递归函数递归栈使用的深度

打赏