題目描述
給定一個(gè)二叉搜索樹的根結(jié)點(diǎn) root, 返回樹中任意兩節(jié)點(diǎn)的差的最小值县忌。
解法
二叉搜索樹屬于有序樹結(jié)構(gòu)古拴，一個(gè)可以利用的特點(diǎn)就是中序遍歷可以得到有序數(shù)組逼泣，得到有序數(shù)組后遍歷一次即可得到兩節(jié)點(diǎn)最小差值休里。
這里不申請(qǐng)數(shù)組空間來(lái)保存樹節(jié)點(diǎn)灶挟，使用兩個(gè)指針?lè)謩e指向上一個(gè)節(jié)點(diǎn)值和最小差值腺占，中序遍歷二叉樹即可得到最小差值淤袜。
# 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
