783.Minimum Distance Between BST Nodes
===

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

[783. Minimum Distance Between BST Nodes](https://leetcode.com/problems/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^5^

**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，這樣就是排序好的值了。
> [name=Marsgoat][time=Feb 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 版
> [name=Ron Chen][time=Fri, 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不過分吧？
> [name=Yen-Chi Chen][time=Fri, Feb 17, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)