530.md

530 Minimum Absolute Difference in BST

Description

link

---

Solution

这里讲一下DFS的时间复杂度判断：如果是最坏情况的话，首先因为初始DFS的循环是O(M + N)，每个点的最大遍历长度是O(MN)，这就是最坏情况的时间复杂度

---

Code

最坏情况下是O(n^2)

Iteration:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        stack = []
        n = float('inf')
        res = float('inf')
        
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                m = root.val
                res = min(abs(m-n), res)
                n = m
                root = root.right
        
        return res

Recursive:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        L = []
        def dfs(node):
            if node.left: dfs(node.left)
            L.append(node.val)
            if node.right: dfs(node.right)
        dfs(root)
        return min(b - a for a, b in zip(L, L[1:]))