530. Minimum Absolute Difference in BST

leetcode easy

#backtracking#csharp#easy#leetcode#math#search#tree#two-pointers

Task

Дано корень бинарного дерева поиска (BST), верните минимальную абсолютную разницу между значениями любых двух разных узлов в дереве.

Пример:

Input: root = [4,2,6,1,3]

Output: 1

C# solution

matched/original

public class Solution {
    private List<int> inorderNodes = new List<int>();
    public int GetMinimumDifference(TreeNode root) {
        InorderTraversal(root);
        int minDifference = int.MaxValue;
        for (int i = 1; i < inorderNodes.Count; i++) {
            minDifference = Math.Min(minDifference, inorderNodes[i] - inorderNodes[i - 1]);
        }
        return minDifference;
    }
    private void InorderTraversal(TreeNode node) {
        if (node == null) return;
        InorderTraversal(node.left);
        inorderNodes.Add(node.val);
        InorderTraversal(node.right);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private List<int> inorderNodes = new List<int>();
    public int GetMinimumDifference(TreeNode root) {
        InorderTraversal(root);
        int minDifference = int.MaxValue;
        for (int i = 1; i < inorderNodes.size(); i++) {
            minDifference = min(minDifference, inorderNodes[i] - inorderNodes[i - 1]);
        }
        return minDifference;
    }
    private void InorderTraversal(TreeNode node) {
        if (node == null) return;
        InorderTraversal(node.left);
        inorderNodes.push_back(node.val);
        InorderTraversal(node.right);
    }
}

Java solution

matched/original

class Solution {
    List<Integer> inorderNodes = new ArrayList<>();
    
    void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        
        inorderTraversal(node.left);
        inorderNodes.add(node.val);
        inorderTraversal(node.right);
    }
    
    int getMinimumDifference(TreeNode root) {
       inorderTraversal(root);
        
        int minDifference = Integer.MAX_VALUE;
        for (int i = 1; i < inorderNodes.size(); i++) {
            minDifference = Math.min(minDifference, inorderNodes.get(i) - inorderNodes.get(i-1));
        }
        
        return minDifference;
    }
};

JavaScript solution

matched/original

var getMinimumDifference = function(root) {
    const inorderNodes = [];
    inorderTraversal(root, inorderNodes);
    let minDifference = Infinity;
    for (let i = 1; i < inorderNodes.length; i++) {
        minDifference = Math.min(minDifference, inorderNodes[i] - inorderNodes[i - 1]);
    }
    return minDifference;
};

function inorderTraversal(node, inorderNodes) {
    if (!node) return;
    inorderTraversal(node.left, inorderNodes);
    inorderNodes.push(node.val);
    inorderTraversal(node.right, inorderNodes);
}

Python solution

matched/original

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        inorderNodes = []
        self.inorderTraversal(root, inorderNodes)
        minDifference = float('inf')
        for i in range(1, len(inorderNodes)):
            minDifference = min(minDifference, inorderNodes[i] - inorderNodes[i - 1])
        return minDifference

    def inorderTraversal(self, node: TreeNode, inorderNodes: List[int]) -> None:
        if not node:
            return
        self.inorderTraversal(node.left, inorderNodes)
        inorderNodes.append(node.val)
        self.inorderTraversal(node.right, inorderNodes)

Go solution

matched/original

import (
    "math"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type Solution struct {
    inorderNodes []int
}

func (s *Solution) getMinimumDifference(root *TreeNode) int {
    s.inorderNodes = []int{}
    s.inorderTraversal(root)
    minDifference := math.MaxInt32
    for i := 1; i < len(s.inorderNodes); i++ {
        minDifference = min(minDifference, s.inorderNodes[i]-s.inorderNodes[i-1])
    }
    return minDifference
}

func (s *Solution) inorderTraversal(node *TreeNode) {
    if node == nil {
        return
    }
    s.inorderTraversal(node.Left)
    s.inorderNodes = append(s.inorderNodes, node.Val)
    s.inorderTraversal(node.Right)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Explanation

Algorithm

Обход дерева в порядке возрастания (инфиксный обход):

Создайте список inorderNodes для хранения значений узлов.

Выполните инфиксный обход дерева, добавляя значения узлов в список.

Нахождение минимальной разницы:

Создайте переменную minDifference и инициализируйте её бесконечностью.

Пройдите по списку inorderNodes, начиная с индекса 1, и найдите минимальную абсолютную разницу между последовательными элементами.

Возврат результата:

Верните minDifference.

😎