Python3、Java 实现「783. 二叉搜索树节点最小距离」

与你一起学算法

发布于 2021-04-28 12:13:17

4320

发布于 2021-04-28 12:13:17

文章被收录于专栏：与你一起学算法

783. 二叉搜索树节点最小距离

题目链接

https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/

也可以点击「阅读原文」直达题目链接。

题目描述

给你一个二叉搜索树的根节点 root，返回树中任意两不同节点值之间的最小差值。

示例 1：

输入：root = [4, 2, 6, 1, 3]
输出：1

示例 2：

输入：root = [1, 0, 48, null, null, 12, 49]
输出：1

提示：

树中节点数目在范围 [2, 100] 内

0 <= Node.val <= 10^5

解题思路

这道题主要是考察二叉搜索树的性质，二叉搜索树的中序遍历得到的结果是升序排列的。要得到树中任意两个不同节点值之间的最小差值，那么只需要比较中序遍历得到的序列的相邻元素，求得最小值就可以了。

这道题看上去有点无从下手的感觉，但是碰到二叉搜索树，就一定要想到的中序遍历是有序的，这几乎是碰到二叉搜索树的必考点。

Python3 代码

# 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 minDiffInBST(self, root: TreeNode) -> int:
        self.inorder_result = []
        self.inorder(root)
        ans = 10 ** 5 + 1
        size = len(self.inorder_result)
        for i in range(1, size):
            ans = min(ans, self.inorder_result[i] - self.inorder_result[i - 1])
        return ans

    def inorder(self, root: TreeNode) -> int:
        if root:
            self.inorder(root.left)
            self.inorder_result.append(root.val)
            self.inorder(root.right)

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.List;
import java.util.ArrayList;
class Solution {
    private List<Integer> list;
    public int minDiffInBST(TreeNode root) {
        list = new ArrayList<>();
        this.inorder(root);
        int ans = 100001;
        for (int i = 1; i < list.size(); ++i) {
            ans = Math.min(ans, list.get(i) - list.get(i - 1));
        }
        return ans;
    }
    public void inorder(TreeNode root) {
        if (root != null) {
            this.inorder(root.left);
            this.list.add(root.val);
            this.inorder(root.right);
        }
    }
}