解题思路

这题其实和LC98.验证二叉搜索树有异曲同工之妙，验证二叉搜索树是判断辅助数组的是否严格递增。

这题是让我们先中序遍历二叉树，然后将val保存进辅助数组nums进行排序，将每个元素与前后元素相减得到的绝对值就是最小绝对差。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        nums = []
        def dfs(root):
            if root is None: return
            dfs(root.left)
            nums.append(root.val)
            dfs(root.right)
        ans = inf
        dfs(root)
        nums.sort()
        for i in range(1, len(nums)):
            if i + 1 < len(nums):
                ans = min(ans, abs(nums[i] - nums[i + 1]))
            ans = min(ans, abs(nums[i] - nums[i - 1]))
        return ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> nums;
        dfs(root, nums);
        sort(nums.begin(), nums.end());
        int ans = INT_MAX;
        for (int i = 1; i < nums.size(); ++i) {
            if (i + 1 < nums.size()) {
                ans = min(ans, abs(nums[i] - nums[i + 1]));
            }
            ans = min(ans, abs(nums[i] - nums[i - 1]));
        }
        return ans;
    }
    // 中序遍历，将val保存辅助数组中
    void dfs(TreeNode* root, vector<int>& nums) {
        if (root == NULL) return;
        dfs(root->left, nums);
        nums.push_back(root->val);
        dfs(root->right, nums);
    }
};

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var nums []int
func getMinimumDifference(root *TreeNode) int {
    ans := math.MaxInt64
    nums = []int{}
    dfs(root)
    sort.Ints(nums)
    for i := 1; i < len(nums); i++ {
        if i + 1 < len(nums){
            ans = min(ans, abs(nums[i] - nums[i + 1]))
        } 
        ans = min(ans, abs(nums[i] - nums[i - 1]))
    }
    return ans
}

func dfs(root *TreeNode) {
    if root == nil{return}
    dfs(root.Left)
    nums = append(nums, root.Val)
    dfs(root.Right)
}

func abs(a int) int{
    if a < 0{return -a}
    return a
}

func min(a int, b int) int{
    if a > b {return b}
    return a
}