欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二叉搜索树的最小绝对差(中序、栈)

程序员文章站 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

相关标签: Tree 中序遍历