LeetCode——二叉搜索树的最小绝对值

野性酷女 2022-12-13 15:29 132阅读 0赞

## 题目 ##

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

**示例：**

**输入：**

1
     \
      3
     /
    2

**输出：**

**解释：**

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

## 题解 ##

从题目中可以获得以下几条信息：

1.  二叉树，且为二叉搜索树，根据二叉搜索树的定义可知二叉树有序
2.  节点为非负值

## 解题思路 ##

### 中序遍历方法 ###

首先我们先分析另外一个问题，如何求一个数组中任意两个元素的差的绝对值的最小值。最简单的 做法就是两层循环遍历数组，计算任意两个元素的差找到最小值。那如果数组有序（升序）呢？是不是绝对值最小的两个元素一定是相邻的两个元素差的绝对值呀。这时候我们只需要遍历一遍数组，计算相邻两个元素差的绝对值即可。

有了上面的问题的思路，接下来看下该问题，我们知道，该树是二叉树，且为二叉搜索树，既然是树，肯定要遍历才能知道树的每个节点的值，又因为是二叉搜索树，那么中序遍历的结果就是有序的且为升序。因此我们可以对该二叉搜索树进行中序遍历，将遍历的节点值存储到一个数组中，之后再按照上面的思路求出最小值即可。此时的时间复杂度![O(n)][O_n]，空间复杂度为![O(n)][O_n]。

### 代码实现 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int getMinimumDifference(TreeNode root) {
            ArrayList<Integer> val = new ArrayList<Integer>();
            inOrder(root, val);
            int res = Integer.MAX_VALUE;
            for (int i=1; i<val.size(); ++i) {
                int diff = Math.abs(val.get(i) - val.get(i-1));
                if (res > diff) {
                    res = diff;
                }
            }
            return res;
        }
    
        public static void inOrder(TreeNode root, ArrayList<Integer> val) {
            if (root == null) {
                return;
            }
            inOrder(root.left, val);
            val.add(root.val);
            inOrder(root.right, val);
        }

## 优化 ##

其实我们不用将遍历的结果保存下来在比较，完全可以在遍历的过程中进行差值计算，这样空间复杂度将为![O(n)][O_n]

### 代码实现 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        int ans;
        int pre;
    
        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);
        }
    }

## **复杂度分析** ##

*  时间复杂度：![O(n)][O_n]，n为树的节点个数，遍历一遍树的所有节点
 *  空间复杂度：![O(n)][O_n]，递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到![O(n)][O_n]的级别

[O_n]: https://private.codecogs.com/gif.latex?O%28n%29