首页 > itarticle > 算法笔记: 力扣#530 二叉搜索树的最小绝对差

算法笔记: 力扣#530 二叉搜索树的最小绝对差

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class :
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(node):
            if node:
                dfs(node.left)
                self.ans = min(self.ans, node.val - self.prev)
                self.prev = node.val
                dfs(node.right)
        self.prev = float('-inf')
        self.ans = float('inf')
        dfs(root)
        return self.ans

Java 实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class  {
    private int ans;
    private int prev;
    private void dfs(TreeNode node){
        if(node != null){
            dfs(node.left);
            int newDist = node.val - prev;
            ans = this.ans < newDist ? ans : newDist;
            prev = node.val;
            dfs(node.right);
        }
    }
    
    public int getMinimumDifference(TreeNode root) {
        ans = Integer.MAX_VALUE;
        prev = -9999;
        dfs(root);
        return ans;
    }
}

时间复杂度

O(N).

空间复杂度

O(L).

链接

530. Minimum Absolute Difference in BST
530. 二叉搜索树的最小绝对差
 (English version) Algorithm Notes: Leetcode#530 Minimum Absolute Difference in BST