题目描述
给定一个二叉搜索树的根结点 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
本文同步分享在 博客“zhipingChen”(JianShu)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。