leetcode-17-BST

530. Minimum Absolute Difference in BST

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

解題思路：

先序周遊，存下來，然後排序，找臨近兩個的最小內插補點。

效率不高。。。後面再想想怎麼改進？？？

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        get(root);
        sort(nodes.begin(), nodes.end());
        int Mini = abs(nodes[0]-nodes[1]);
        for (int i = 1; i < nodes.size(); i++) {
            Mini = min(Mini, abs(nodes[i]-nodes[i-1]));
        }
        return Mini;
    }
    void get(TreeNode* root) {
        if (root)
            nodes.push_back(root->val);
        if (root->left)
            get(root->left);
        if (root->right)
            get(root->right);
    }
private:
    vector<int> nodes;
    
};      

235. Lowest Common Ancestor of a Binary Search Tree

解題思路：

直接找。。如果p,q的值大于root，就到右子樹找；如果都小于root，就到左子樹找，否則傳回root。

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val < root->val && q->val < root->val)
            return lowestCommonAncestor(root->left, p, q);
        if (p->val > root->val && q->val > root->val)
            return lowestCommonAncestor(root->right, p, q);
        return root;
    }