783.Minimum Distance Between BST Nodes

tags: Easy,Tree,BFS,DFS,Binary Tree

783. Minimum Distance Between BST Nodes

題目描述

Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.

範例

Example 1:

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

Example 2:

Input: root = [1,0,48,null,null,12,49]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 100].
• 0 <= Node.val <= 10⁵

Note: This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/

解答

Javascript

function miniDiffInBST(root) {
  let min = Infinity;
  let node = root;
  let prev = null; // 用來記錄前一個node的值
  const stack = [];
  while (stack.length || node !== null) {
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }

    node = stack.pop();
    if (prev !== null) {
      min = Math.min(min, node.val - prev);
      prev = node.val;
    } else {
      prev = node.val;
    }
      
    node = node.right;
  }

  return min;
}

我超笨，本來做DFS取整棵樹的值，排序後依序相減，找到差最小的，完全忘記他是BST，可以直接用Inorder Traversal，這樣就是排序好的值了。
MarsgoatFeb 17, 2023

Python

class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        self.mn, self.pre = math.inf, None

        def dfs(root):
            if not root:
                return

            dfs(root.left)
            
            if self.pre:
                self.mn = min(self.mn, abs(root.val - self.pre.val))
            self.pre = root
            
            dfs(root.right)

        dfs(root)

        return self.mn

樓上做法的 Recursive 版
Ron ChenFri, Feb 17, 2023

C++

class Solution {
public:
    int minDiffInBST(TreeNode* root, int alpha = -999999, int beta = 999999) {
        if (!root) return INT_MAX;
        int ans = min(root->val - alpha, beta - root->val);
        ans = min(ans, minDiffInBST(root->left, alpha, root->val));
        ans = min(ans, minDiffInBST(root->right, root->val, beta));
        return ans;
    }
};

畢竟大家都是學對局的，來點AlphaBeta不過分吧？
Yen-Chi ChenFri, Feb 17, 2023

Reference

回到題目列表