題目敘述

題目難度： Easy
題目敘述：給定一個 Binary Search Tree (BST) 的 root ，回傳樹中任意兩個節點的絕對值當中最小的。

解法

一開始的想法

首先 Binary Search Tree 的特性就是對於任意節點， 其左子樹必定 < 當前節點 < 右子樹。

因此可以判斷，在對這顆樹進行 Inorder Traversal 的過程中，相鄰節點的差值會是最小的，不存在跨一個節點之間差值更小的問題

所以基本上我的想法就是跑一遍 Inorder Traversal，將節點記錄到一個 list，在 list 中再計算差值．但這樣缺點就是 runtime 會增加。

我的解法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> nodes;
    vector<int> nodeDifferences;
    vector<int>::iterator result;

    void inorder(TreeNode *current){
        if(current== nullptr) return;
        inorder(current->left);
        nodes.push_back(current->val);
        inorder(current->right);
    }


    int getMinimumDifference(TreeNode* root){
        if(root == nullptr) return 0;
        inorder(root);
        for(int i=1; i< nodes.size(); i++){
            nodeDifferences.push_back(abs(nodes[i]-nodes[i-1]));
        }
        result = min_element(nodeDifferences.begin(), nodeDifferences.end());
        return *result;
    }

};

上面在 void inorder(TreeNode *current) 中紀錄了節點值，記錄完畢後回到 caller int getMinimumDifference(TreeNode* root) 這時候依序將相鄰節點差值計算出。

最後透過一格 vector iterator 去找回傳list當中最小的值。

要使用這個 iterator 必須 include 標頭 <algorithm>

執行結果

更好的做法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int diff = INT_MAX;
    TreeNode *prev = nullptr;

    void dfs(TreeNode* current){
        if(current==nullptr) return;
        dfs(current->left);
        if(prev!= nullptr) diff = min(diff, abs(current->val - prev->val));
        prev = current;
        dfs(current->right);
    }


    int getMinimumDifference(TreeNode* root){
        dfs(root);
        return diff;
    }

};