LeetCode——783. 二叉搜索树节点最小距离(Java)
2021/4/13 12:29:01
本文主要是介绍LeetCode——783. 二叉搜索树节点最小距离(Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
题干: 给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。 示例1: 输入:root = [4,2,6,1,3] 输出:1 示例2: 输入:root = [1,0,48,null,null,12,49] 输出:1
题解思路
返回节点差值的最小值,这里因为是二叉搜索树,所以如果存在差值最小的数,所以一定是相邻的差值 这样问题就简化成了中序遍历二叉树,在运算中加入做差比较差值的操作,因为中序遍历二叉排序树元素是递增的
正确代码
class Solution { int pre; int ans; public int minDiffInBST(TreeNode root) { pre = -1; ans = Integer.MAX_VALUE; dfs(root); return ans; } private 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); } }
总结
二叉树的问题其实总离不开遍历问题,无论是找节点还是求树的高度都离不开这几种遍历 如果文章存在问题或者有更好的题解,欢迎在评论区斧正和评论,各自努力,你我最高处见
这篇关于LeetCode——783. 二叉搜索树节点最小距离(Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29DataGrip使用ssh连接数据库的操作流程
- 2024-05-28SpringBoot3.2更新声明!
- 2024-05-28中外程序员到底有啥区别?
- 2024-05-25外企也半夜发布上线吗?
- 2024-05-24鸿蒙原生应用再新丁!芒果TV 入局鸿蒙
- 2024-05-22基本概念
- 2024-05-22检索数据
- 2024-05-22排序数据
- 2024-05-22基础过滤数据
- 2024-05-22通过逻辑操作符过滤数据