手撸二叉树之二叉搜索树的最小绝对差

手撸二叉树之二叉搜索树的最小绝对差

今天给大家带来的关于二叉树相关的算法题是二叉搜索树的最小绝对差，正文如下：

题目

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

示例：

输入： 1 \ 3 / 2

解题思路

根据题意，该二叉树是一棵二叉搜索树，所以我们可以用中序遍历的方式来遍历整棵二叉树，得到的将是一个有序的数组，然后再循环遍历该数组，依次遍历数组中的值，来得到最小绝对差；

上面的解法是一种可行方案，另外我们还能用边遍历边找的方式来得出最小绝对差，具体思路如下：

定义一个全局变量 ans 用于记录最小绝对差，再定义一个全局变量，用于记录二叉树遍历的上一个值；如果遇到节点为 null, 则直接返回；中序遍历该二叉树，如果 pre = -1，则表示该节点是根节点，并将根节点的值赋值给 pre, 否则，则计算当前节点与先前节点差的绝对值，并与 ans 比较，取最小值赋值给 ans;

代码实现

/** * 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; * } * } */class Solution { int ans; int pre; public int getMinimumDifference(TreeNode root) { ans = Integer.MAX_VALUE; pre = -1; inOrder(root); return ans; } public void inOrder(TreeNode node){ if (node == null) { return; } inOrder(node.left); if (pre == -1) { pre = node.val; } else

最后

复杂度分析：

时间复杂度：O(n)，其中 n 为二叉搜索树节点的个数。每个节点在中序遍历中都会被访问一次且只会被访问一次，因此总时间复杂度为 O(n)。空间复杂度：O(n)。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 O(n) 级别。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。