手撸二叉树之二叉搜索树的最小绝对差
发布于: 4 小时前
Hello, 大家好，今天是我参加 9 月更文的第 4 天，今天给大家带来的关于二叉树相关的算法题是二叉树的所有路径，正文如下：
题目
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
示例：
复制代码
解题思路
根据题意，该二叉树是一棵二叉搜索树，所以我们可以用中序遍历的方式来遍历整棵二叉树，得到的将是一个有序的数组，然后再循环遍历该数组，依次遍历数组中的值，来得到最小绝对差；
上面的解法是一种可行方案，另外我们还能用边遍历边找的方式来得出最小绝对差，具体思路如下：
定义一个全局变量 ans 用于记录最小绝对差，再定义一个全局变量，用于记录二叉树遍历的上一个值；
如果遇到节点为 null, 则直接返回；
中序遍历该二叉树，如果 pre = -1，则表示该节点是根节点，并将根节点的值赋值给 pre, 否则，则计算当前节点与先前节点差的绝对值，并与 ans 比较，取最小值赋值给 ans;
代码实现
复制代码
最后
复杂度分析：
时间复杂度：O(n)，其中 n 为二叉搜索树节点的个数。每个节点在中序遍历中都会被访问一次且只会被访问一次，因此总时间复杂度为 O(n)。
空间复杂度：O(n)。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到 O(n) 级别。
版权声明: 本文为 InfoQ 作者【HelloWorld杰少】的原创文章。
原文链接:【http://xie.infoq.cn/article/cc1379a5d0391a82cbeea539c】。文章转载请联系作者。
佛系编码 2019.05.13 加入
红鲤鱼与绿鲤鱼与驴。
评论