LeetCode530. 二叉搜索树的最小绝对差（中序、栈）

1、题目描述

https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。树中至少有 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://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/solution/zhong-xu-bian-li-tuan-mie-xi-lie-er-cha-sou-suo-sh/