二叉搜索树最小差值

[编程题]二叉搜索树最小差值

热度指数：1132 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉搜索树，请你返回树中任意两节点之差的最小值。

数据范围：二叉树节点数满足 $2 \le n \le 10^5 \$ ，二叉树的节点值满足 $0 \le val \le 10^9 \$ ，保证每个节点的值都不同

示例1

输入

{2,1,3,#,#,#,4}

输出

示例2

输入

{3,1,5,#,#,#,9}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python 3

大海里捞offer

思路也是中序遍历但是超时了。

class Solution:

    def inorderTravseral(self,root):
        if not root:
            return []
        return self.inorderTravseral(root.left) + [root.val] + self.inorderTravseral(root.right)

    def minDifference(self , root: TreeNode) -> int:
        re = self.inorderTravseral(root)
        ans = float('inf')
        for i in range(len(re)-2):
            ans = min(ans, re[i+1] - re[i])
        return ans

发表于 2022-07-02 20:29:59 回复(1)