专栏首页编程理解Leetcode 783. 二叉搜索树结点最小距离

Leetcode 783. 二叉搜索树结点最小距离

题目描述

给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。

解法

二叉搜索树属于有序树结构,一个可以利用的特点就是中序遍历可以得到有序数组,得到有序数组后遍历一次即可得到两节点最小差值。

这里不申请数组空间来保存树节点,使用两个指针分别指向上一个节点值和最小差值,中序遍历二叉树即可得到最小差值。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minDiffInBST(self, root: TreeNode) -> int:
        self.lastVal,self.ret=None,None
        def inOrderTraversal(node):
            if node:
                inOrderTraversal(node.left)
                if self.ret!=None:
                    self.ret=min(self.ret,node.val-self.lastVal)
                elif self.lastVal!=None:
                    self.ret=node.val-self.lastVal
                self.lastVal=node.val
                inOrderTraversal(node.right)
        inOrderTraversal(root)
        return self.ret

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 501. 二叉搜索树中的众数

    给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。

    zhipingChen
  • Leetcode 206. 反转链表

    遍历链表,以 cur 表示当前节点,以 last 表示上一个节点,将 cur 的 next 指针指向 last 即可。

    zhipingChen
  • Leetcode 188. 买卖股票的最佳时机 IV

    输入: [2,4,1], k = 2 输出: 2 解释: 在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这...

    zhipingChen
  • 数字华容道03:首页创建

    整个布局采用 QVBoxLayout (竖型布局)。最上方的“数字华容道”字样是一张图片,采用QLabel进行展示。下面几个选择难度的按钮和排行榜按钮采用 QP...

    王强
  • tornado学习笔记

    tornado是默认自动开启转义的,大家可以根据需求来选是否转义,但是要知道转义的本意是来防止浏览器意外执行恶意代码的,所以去掉转义的时候需要谨慎选择

    py3study
  • 利用PyQt5+Matplotlib 绘制静态/动态图的实现代码

    静态作图:数据作图,取决于作图函数,可自行修改 动态作图:产生数据,获取并更新数据,最后刷新显示,可用于实现数据实时采集并显示的场景

    砸漏
  • 三、wss连接B站弹幕

    py3study
  • 高效处理流量加解密——Burpy

    先来地址:Github: https://github.com/mr-m0nst3r/Burpy

    用户2202688
  • bs4爬虫实战三:获取电影信息并存入mysql数据库

    这次爬虫的目标网站是:http://dianying.2345.com,爬虫的搜索目标仅限于今年的电影,在网站打开搜索,在年代中选择2018

    py3study
  • python小练习----秒表

    from tkinter import * import time class StopWatch(Frame):     '''实现一个秒表部件'''    ...

    用户7886150

扫码关注云+社区

领取腾讯云代金券