代码随想录算法训练营第21天 | 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先

TFTree 发布于 2022-12-06 793 次阅读

530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

思路:使用中序遍历二叉搜索树，找相邻两个节点间差值的最小值

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int ans = INT_MAX;
    TreeNode* pre = nullptr;
    void getMin(TreeNode* root) {
        if(root == nullptr) {
            return;
        }

        getMin(root->left);

        if(pre != nullptr) {
            ans = min(ans, root->val - pre->val);
        }
        pre = root;

        getMin(root->right);
    }
    int getMinimumDifference(TreeNode* root) {
        getMin(root);
        return ans;
    }
};

标准答案

递归法

//时间复杂度O(n),空间复杂度O(n)
class Solution {
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur) {
    if (cur == NULL) return;
    traversal(cur->left);   // 左
    if (pre != NULL){       // 中
        result = min(result, cur->val - pre->val);
    }
    pre = cur; // 记录前一个
    traversal(cur->right);  // 右
}
public:
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};

迭代法

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        int result = INT_MAX;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top();
                st.pop();
                if (pre != NULL) {              // 中
                    result = min(result, cur->val - pre->val);
                }
                pre = cur;
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

501. 二叉搜索树中的众数 - 力扣（LeetCode）

思路:

  • 使用递归中序遍历二叉搜索树，用unordered_map来存储二叉树中的值与出现次数，出现次数的最大值在cmax中存储，遍历二叉搜索树完成以后遍历一次unordered_map，遇到出现次数等于cmax的就加入结果数组
  • 不使用unordered_map的方法是递归中序遍历二叉树的时候，每次都先把符合cnt == cmax的值放入结果数组，但如果发现cnt > cmax，就将结果数组清空，然后再重新把值放进结果数组，这样就保证最后结果数组中储存的值是众数

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int cnt = 1;
    int cmax = 1;
    unordered_map<int, int> up;
    TreeNode* pre = nullptr;
    void findAll(TreeNode* cur) {
        if(cur == nullptr) {
            return;
        }
        findAll(cur->left);
        up[cur->val]++;
        if(pre != nullptr && pre->val == cur->val) {
            cnt++;
            cmax = max(cnt, cmax);
        }
        else if(pre != nullptr && pre->val != cur->val) {
            cnt = 1;
        }
        pre = cur;
        findAll(cur->right);
    }
    vector<int> findMode(TreeNode* root) {
        findAll(root);
        vector<int> ans;
        for(auto a : up) {
            if(a.second == cmax) {
                ans.push_back(a.first);
            }
        }
        return ans;
    }
};

递归中序遍历(不使用unordered_map，一遍循环找到所有众数)

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    TreeNode* pre = nullptr;
    int cnt = 1;
    int cmax = 1;
    void find_all(vector<int> & ans, TreeNode* root) {
        if(root == nullptr) {
            return;
        }
        find_all(ans, root->left);
        if(pre == nullptr) {
            cnt = 1;
        }
        else if(pre->val == root->val) {
            cnt++;
        }
        else {
            cnt = 1;
        }
        pre = root;
        if(cnt == cmax) {
            ans.push_back(root->val);
        }
        if(cnt > cmax) {
            cmax = cnt;
            ans.clear();
            ans.push_back(root->val);
        }
        find_all(ans, root->right);
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> ans;
        find_all(ans, root);
        return ans;
    }
};

标准答案

适用于所有二叉树的解法

//时间复杂度O(nlogn),空间复杂度O(n)
class Solution {
private:
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;
}
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> map; // key:元素，value:出现频率
        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++) {
            // 取最高的放到result数组中
            if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
            else break;
        }
        return result;
    }
};

递归法(只遍历一次)

//时间复杂度O(n),空间复杂度O(n)
class Solution {
private:
    int maxCount = 0; // 最大频率
    int count = 0; // 统计频率
    TreeNode* pre = NULL;
    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中
            result.push_back(cur->val);
        }

        if (count > maxCount) { // 如果计数大于最大值频率
            maxCount = count;   // 更新最大频率
            result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
            result.push_back(cur->val);
        }

        searchBST(cur->right);      // 右
        return ;
    }

public:
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        TreeNode* pre = NULL; // 记录前一个节点
        result.clear();

        searchBST(root);
        return result;
    }
};

迭代法

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        int maxCount = 0; // 最大频率
        int count = 0; // 统计频率
        vector<int> result;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点，访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top();
                st.pop();                       // 中
                if (pre == NULL) { // 第一个节点
                    count = 1;
                } else if (pre->val == cur->val) { // 与前一个节点数值相同
                    count++;
                } else { // 与前一个节点数值不同
                    count = 1;
                }
                if (count == maxCount) { // 如果和最大值相同，放进result中
                    result.push_back(cur->val);
                }

                if (count > maxCount) { // 如果计数大于最大值频率
                    maxCount = count;   // 更新最大频率
                    result.clear();     // 很关键的一步，不要忘记清空result，之前result里的元素都失效了
                    result.push_back(cur->val);
                }
                pre = cur;
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

思路:

  • 递归后序遍历该数组，如果root == nullptr，则直接返回nullptr，然后获取左子树是否包含目标值和右子树是否包含目标值，如果包含会返回离那个目标值最近的祖先节点(可以是自己)，否则返回空节点，然后进行中间的处理，判断root即中间值是否是目标值中的一个，如果是则直接返回root，这边直接返回是因为把左右子树有目标值或者没目标值的情况都包含了，如果不是则继续判断，左右子树中有一个非nullptr就返回该子树的返回值，否则返回nullptr，最后如果左右都有值则返回root

我的AC代码

递归法

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    TreeNode* findAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr) {
            return nullptr;
        }
        TreeNode* left = findAncestor(root->left, p, q);
        TreeNode* right = findAncestor(root->right, p, q);
        if(root == p || root == q) {
            return root;
        }
        if(left == nullptr && right != nullptr) {
            return right;
        }
        if(left != nullptr && right == nullptr) {
            return left;
        }
        if(left == nullptr && right == nullptr) {
            return nullptr;
        }
        return root;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return findAncestor(root, p, q);   
    }
};

标准答案

递归法

//时间复杂度O(n),空间复杂度O(n)
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 right;
        else if (left != NULL && right == NULL) return left;
        else  { //  (left == NULL && right == NULL)
            return NULL;
        }

    }
};