day18二叉树6

530.二叉搜索树的最小绝对差

class Solution {
public:
    int result = INT_MAX;
    int num1 = INT_MAX;
    int num2 = -100001;
    int getMinimumDifference(TreeNode* root) {
        if (root == nullptr) {
            return result;
        }
        int left = getMinimumDifference(root->left);
        num1 = num2;
        num2 = root->val;
        result = min(result, num2 - num1);
        int right = getMinimumDifference(root->right);
        return result;
    }
};

优雅版（指针）：

class Solution {
private:
    int result = INT_MAX;
    TreeNode *pre = nullptr;
    void traversal(TreeNode *cur) {
        if (cur == nullptr) {
            return;
        }
        traversal(cur->left);
        if (pre) {
            result = min(result, cur->val - pre->val);
        }
        pre = cur;
        traversal(cur->right);
    }
public:
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};

501.二叉搜索树中的众数

递归法（很巧妙，但是自己没写出来）：

class Solution {
private:
    int maxCount = 0;
    int count = 0;
    TreeNode *pre = nullptr;
    vector<int> res;
    void searchBST(TreeNode *cur) {
        if (cur == nullptr) {
            return;
        }
        searchBST(cur->left);
        if (pre == nullptr || pre->val != cur->val) {
            count = 1;
        }
        else {
            count ++;
        }
        pre = cur;
        if (count == maxCount) {
            res.push_back(cur->val);
        }
        if (count > maxCount) {
            maxCount = count;
            res.clear();
            res.push_back(cur->val);
        }
        searchBST(cur->right);
    }

public:
    vector<int> findMode(TreeNode* root) {
        searchBST(root);
        return res;
    }
};

迭代法：

class Solution {
private:
    unordered_map<int, int> umap;
    void traversal(TreeNode *cur) {
        if (cur == nullptr) {
            return;
        }
        traversal(cur->left);
        umap[cur->val] ++;
        traversal(cur->right);
    }

    bool static cmp(const pair<int, int> &a, const pair<int, int> &b) {
        return a.second > b.second;
    }

public:
    vector<int> findMode(TreeNode* root) {
        traversal(root);
        vector<int> res;
        vector<pair<int, int>> vec(umap.begin(), umap.end());
        sort(vec.begin(), vec.end(), cmp);
        res.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i ++) {
            if (vec[i].second != vec[0].second) {
                break;
            }
            res.push_back(vec[i].first);
        }
        return res;
    }
};

236. 二叉树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == q || root == p || root == nullptr) {
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != nullptr && right != nullptr) {
            return root;
        }
        if (left == nullptr) {
            return right;
        }
        else if (right == nullptr) {
            return left;
        }
        else {
            return nullptr;
        }
    }
};