[数据结构与算法]Leetcode二叉树（四）

617. 合并二叉树

力扣题目链接

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == NULL)   return root2;
        if(root2 == NULL)   return root1;
        TreeNode* root = new TreeNode(0);
        root->val = root1->val + root2->val;
        root->left = mergeTrees(root1->left, root2->left);
        root->right = mergeTrees(root1->right, root2->right);
        return root;
    }
};

700. 二叉搜索树中的搜索

力扣题目链接

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while(root != NULL){
            if(root->val > val) root = root->left;
            if(root->val < val) root = root->right;
            if(root->val == val)    return root;
        }
        return NULL;
    }
};

98. 验证二叉搜索树

力扣题目链接

class Solution {
public:
    vector<int> vec;
    void traversal(TreeNode* root){
        if(root == NULL)    return;
        traversal(root->left);
        vec.push_back(root->val);
        traversal(root->right);
    }
    bool isValidBST(TreeNode* root) {
        traversal(root);
        for(int i = 1; i < vec.size(); i++){
            if(vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};

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

力扣题目链接

class Solution {
public:
    vector<int> vec;
    void traversal(TreeNode* root){
        if(root == NULL)    return;
        traversal(root->left);
        vec.push_back(root->val);
        traversal(root->right);
    }
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        if(vec.size() < 2)  return 0;
        int result = INT_MAX;
        for(int i = 1; i < vec.size(); i++){
            result = min(result, vec[i] - vec[i - 1]);
        }
        return result;
    }
};

501. 二叉搜索树中的众数

力扣题目链接

class Solution {
public:
    void searchBST(TreeNode * cur, unordered_map<int, int>& map){
        if(cur == NULL) return;
        map[cur->val]++;
        searchBST(cur->left, map);
        searchBST(cur->right, map);
        return;
    }    
    bool static cmp(const pair<int, int>& a, const pair<int, int> &b){
        return a.second > b.second;
    }
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> map;
        vector<int> result;
        if(root == NULL)    return result;
        searchBST(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp);
        result.push_back(vec[0].first);
        for(int i = 1; i < vec.size(); i++){
            if(vec[i].second == vec[0].second)  result.push_back(vec[i].first);
            else break;
        }
        return result;
    }
};

class Solution {
public:
    int maxCount;
    int count;
    TreeNode* pre;
    vector<int> result;
    void searchBST(TreeNode* cur){
        if(cur == NULL) return;
        searchBST(cur->left);

        if(pre == NULL) count = 1;
        else if(pre->val == cur->val) count++;
        else count = 1;      
        pre = cur;

        if(count == maxCount)   result.push_back(cur->val);
        if(count > maxCount){
            maxCount = count;
            result.clear();
            result.push_back(cur->val);
        }

        searchBST(cur->right);
        return;
    }
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        TreeNode* pre = NULL;
        searchBST(root);
        return result;
    }
};

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

力扣题目链接

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