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

题目描述

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

解法

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

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

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, x):
4#         self.val = x
5#         self.left = None
6#         self.right = None
7
8class Solution:
9    def minDiffInBST(self, root: TreeNode) -> int:
10        self.lastVal,self.ret=None,None
11        def inOrderTraversal(node):
12            if node:
13                inOrderTraversal(node.left)
14                if self.ret!=None:
15                    self.ret=min(self.ret,node.val-self.lastVal)
16                elif self.lastVal!=None:
17                    self.ret=node.val-self.lastVal
18                self.lastVal=node.val
19                inOrderTraversal(node.right)
20        inOrderTraversal(root)
21        return self.ret

本文同步分享在 博客“zhipingChen”（JianShu）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。