二叉搜索树最小差值

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

热度指数：1399 时间限制：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，点此查看相关信息

算法知识视频讲解

Python3

danspace

class Solution:
    def minDifference(self , root: TreeNode) -> int:
        # write code here
        l = []
        def inOrder(root):
            if not root:
                return
            inOrder(root.left)
            l.append(root.val)
            inOrder(root.right)
        inOrder(root)
        ans = float('inf')
        for i in range(1, len(l)):
            ans = min(ans, l[i] - l[i-1])
        return ans

发表于 2023-04-27 16:30:17 回复(0)