二叉搜索树的最小绝对差(中序、栈)
程序员文章站
2022-06-15 19:09:59
1、题目描述https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。树中至少有 2 个节点。2、代码详解中序遍历(利用栈)中序遍历二叉搜索树,第一个结点外的每个节点与其前一节点的差值,如果该值小于最小绝对差,就用它更新最小绝对差(初始可设为无穷)。没有必要取绝对值 abs(cur_val - pre_val), 二....
1、题目描述
给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。树中至少有 2 个节点。
2、代码详解
中序遍历(利用栈)
中序遍历二叉搜索树,第一个结点外的每个节点与其前一节点的差值,如果该值小于最小绝对差,就用它更新最小绝对差(初始可设为无穷)。
没有必要取绝对值 abs(cur_val - pre_val), 二叉搜索树中序排列,当前值cur_val一定大于pre_val,cur_val - pre_val 一定是正数。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
stack = []
p = root
pre_val = -float('inf') # 初始值设负无穷
min_val = float('inf')
while p or stack:
while p:
stack.append(p)
p = p.left # 左
p = stack.pop()
cur_val = p.val
if cur_val - pre_val < min_val:
min_val = cur_val - pre_val
pre_val = cur_val
p = p.right # 右
return min_val
时间复杂度:O(N),N为树中节点个数
空间复杂度:O(log(N))
附:二叉树的中序遍历迭代法:用栈,再用一个指针模拟访问过程
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
# 用p当做指针
p = root
while p or stack:
# 把左子树压入栈中
while p:
stack.append(p)
p = p.left
# 输出 栈顶元素
p = stack.pop()
res.append(p.val)
# 看右子树
p = p.right
本文地址:https://blog.csdn.net/IOT_victor/article/details/109038537