【LeetCode 530】二叉搜索树的最小绝对差

叁歲伎倆 2022-12-05 00:49 168阅读 0赞

#### 题目描述 ####

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

示例：

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

提示：

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

#### 解题思路 ####

这道题目比较简单，先回忆一下二叉搜索树的特征：左子树的值始终小于父节点的值，右子树的值始终大于父节点的值。那

还有很重要的一点：在二叉搜索树的遍历中，中序遍历出来的结果是一个升序的数组。

那我们就可以进行中序遍历，并比较相邻的节点的值，始终保持结果是当前最小的值。

#### 代码实现 ####

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
    /** * @param {TreeNode} root * @return {number} */
    var getMinimumDifference = function(root) { 
        let pre = null
        let min = Infinity
        
        let inOrderTravel = (root) => { 
            if(root){ 
                inOrderTravel(root.left)
                if(pre){ 
                    min = Math.abs(root.val - pre.val) < min ? Math.abs(root.val - pre.val) : min
                }
                pre = root
                inOrderTravel(root.right)
            }
        }
        inOrderTravel(root)
        return min
    };

#### 提交结果 ####

![在这里插入图片描述][20200908144851652.png]

[783]: https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
[20200908144851652.png]: /images/20221123/bdbc5d25e84a4e1ca6411c2664f1992f.png?