专栏首页赵俊的Java专栏LeetCode 783 Minimum Distance Between BST Nodes

LeetCode 783 Minimum Distance Between BST Nodes

题意

给予一颗二叉搜索树, 返回任意两个节点之间的最小相差值.

注: 树至少有两个节点.

例 :

给予树:


   1
    \
     4
    / \
   2   7


返回: 1 (1 和 2 之间相差 1).

解法

这道题很像: Minimum Absolute Difference in BST, 解法甚至可以通用.

因为是一颗二叉搜索树, 所以采用中序遍历可以得到所有值从小到大的排列, 那么将每个节点与上个节点的值 prev 进行比较得出相差值 answer, 判断相差值与上个相差值, 将更小的存起来. 直到遍历完整棵树.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int prev = -1;
    private int answer = Integer.MAX_VALUE;
    public int minDiffInBST(TreeNode root) {
        if (root.left != null) {
            minDiffInBST(root.left);
        }

        if (prev != -1) {
            answer = Math.min(answer, root.val - prev);
        }
        
        prev = root.val;

        if (root.right != null) {
            minDiffInBST(root.right);
        }
        return answer;
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Minimum Distance Between BST Nodes. Memory Usage: 33.5 MB, less than 100.00% of Java online submissions for Minimum Distance Between BST Nodes.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 530 Minimum Absolute Difference in BST

    因为是一颗二叉搜索树, 所以采用中序遍历可以得到所有值从小到大的排列, 那么将每个节点与上个节点的值 prev 进行比较得出相差值 answer, 判断相差值与...

    一份执着✘
  • 爬楼梯

    一份执着✘
  • LeetCode 938 Range Sum of BST

    给予一颗二叉搜索树, 返回区间 L - R 之间的所有值的总和. 二叉搜索树中没有重复值.

    一份执着✘
  • LeetCode 530 Minimum Absolute Difference in BST

    因为是一颗二叉搜索树, 所以采用中序遍历可以得到所有值从小到大的排列, 那么将每个节点与上个节点的值 prev 进行比较得出相差值 answer, 判断相差值与...

    一份执着✘
  • 二叉树由浅至深(上)

    树有很多种表示方式,如:双亲表示法,孩子表示法、孩子兄弟表示法等等。这里简单了解其中最常用的孩子兄弟表示法。

    海盗船长
  • [LeetCode] 938. Range Sum of BST 二叉搜索树的区间和

    Given the root node of a binary search tree, return the sum of values of all nod...

    lucifer210
  • [Swagger] Springfox Swagger 项目接口自动化管理平台

    swagger相关maven文件放在公共父层,在parent-pom中,springfox的scope设置为provided,Springfox以及其依赖的ja...

    架构探险之道
  • Tree - 110. Balanced Binary Tree

    Given a binary tree, determine if it is height-balanced.

    用户5705150
  • 打印字符图形(蓝桥杯基础题 Java版)

    问题描述 利用字母可以组成一些美丽的图形,下面给出了一个例子: ABCDEFG BABCDEF CBABCDE DCBABCD EDCBABC 这...

    张俊怡
  • Cassandra数据操作管理工具tableplus

    Cassandra是一个NoSQL数据库,具有类SQL CQL入口,基本语法与SQL保持一致。其实笔者认为 Cassandra的自带的cqlsh已经满足本的需求...

    py3study

扫码关注云+社区

领取腾讯云代金券