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

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

代码随想录链接

题目

返回给定的二叉搜索树内, 节点之间最小的差值.

自己的思路

二叉搜索树的中序遍历的结果是有序的, 在其中中找相邻值最小的即可.

题解

递归法:

class Solution {
private:
    vector<int> result;
    void traversal(TreeNode *root) {    // 中序遍历, 记录结果
        if (!root) return;
        traversal(root -> left);
        result.push_back(root -> val);
        traversal(root -> right);
    }
public:
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        int minGap = INT_MAX;
        for (int i = 1; i < result.size(); i++)     // 找相邻数据最小的差值
            if (result[i] - result[i - 1] < minGap)
                minGap = result[i] - result[i - 1];
        return minGap;
    }
};

迭代法:

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        if (!root) return 0;
        vector<int> result;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {   // 中序遍历
            TreeNode *node = st.top();
            if (node) {
                st.pop();

                if (node -> right) st.push(node -> right);

                st.push(node);
                st.push(nullptr);

                if (node -> left) st.push(node -> left);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node -> val);
            }
        } 
        int minGap = INT_MAX;
        for (int i = 1; i < result.size(); i++)     // 找最小差值
            if (result[i] - result[i - 1] < minGap)
                minGap = result[i] - result[i - 1];
        return minGap;
    }
};

501.二叉搜索树中的众数

代码随想录链接

题目

给定一个二叉搜索树, 返回其中的众数.

自己的思路

可以将全部节点遍历一遍, 通过map记录出现次数, 再进行排序得到, 但这样就和普通的二叉树没区别了.

二叉搜索树的中序遍历是有序的, 相同的数都会排在一起, 可以通过这个特性, 在中序遍历的基础上, 找到众数.

题解

递归法:

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; // 第一个节点, pre为空的情况的处理
        else if (pre -> val == cur -> val) count++; // 与上一个遍历的节点的值相同, 当前值出现次数+1
        else count = 1;             // 遇上一个点值不同, 重置出现次数

        pre = cur;                  // pre后移

        if (count == maxCount) result.push_back(cur -> val);    // 当前值统计次数和最大次数一致, 是可能得众数, 加入结果中

        if (count > maxCount) {     // 若当前值出现的次数超过了前面值出现最多的次数, 证明众数的要求提高了
            maxCount = count;       // 更新maxCount
            result.clear();         // 之前的数都不是众数
            result.push_back(cur -> val);
        }

        searchBST(cur -> right);
    }
public:
    vector<int> findMode(TreeNode* root) {
        searchBST(root);
        return this -> result;
    }
};

迭代法: (也是中序遍历, 甚至直接把上面对于中序遍历的中间节点的处理直接复制过来都没问题)

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        int maxCount = 0;
        int count = 0;
        TreeNode *pre = nullptr;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            TreeNode *node = st.top();
            if (node) {
                st.pop();
                if (node -> right) st.push(node -> right);
                st.push(node);
                st.push(NULL);
                if (node -> left) st.push(node -> left);
            } else {            // 和递归法中一样的处理思路
                st.pop();
                node = st.top();
                st.pop();
                if (pre == NULL) count = 1;
                else if (pre -> val == node -> val) count++;
                else count = 1;
                pre = node;
                if (count == maxCount) result.push_back(node -> val);
                if (count > maxCount) {
                    maxCount = count;
                    result.clear();
                    result.push_back(node -> val);
                }
            }
        }
        return result;
    }
};

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

代码随想录链接

题目

给定一棵二叉树和其中的两个节点, 返回离这两个节点最近的公共祖先.

自己的思路

自己是想按照之前写二叉树的所有叶子路径那样来写这个题, 确实也实现了, 但是提交的时候就超时了.

看了卡尔哥的写法, 才发现不用写我那样复杂.

题解

自己想的通过遍历并记录路径来做的方法:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return nullptr;
        vector<vector<TreeNode*>> paths;    // 记录节点的路径
        vector<TreeNode*> p_path;           // 记录p节点的路径
        vector<TreeNode*> q_path;           // 记录q节点的路径
        stack<TreeNode*> st;                // 用于遍历的栈
        st.push(root);
        paths.push_back(vector<TreeNode*>{root});
        bool hasFoundp = false;             // 是否找到节点的标记
        bool hasFoundq = false;
        while (!st.empty() && (!hasFoundp || !hasFoundq)) { // 如果栈不为空, 且q p没有全部找到, 则继续遍历
            auto node = st.top(); st.pop();
            auto path = paths.back(); paths.pop_back();

            if (!hasFoundp && node == p) {  // 如果找到了p节点, 就标记p的路径
                hasFoundp = true;
                copy(path.begin(), path.end(), back_inserter(p_path));
            }

            if (!hasFoundq && node == q) {  // 找到了q节点, 标记q的路径
                hasFoundq = true;
                copy(path.begin(), path.end(), back_inserter(q_path));
            }

            if (node -> right) {            // 右节点和其路径压栈
                st.push(node -> right);
                path.push_back(node -> right);
                paths.push_back(path);
                path.pop_back();
            }

            if (node -> left) {             // 左节点和其路径压栈
                st.push(node -> left);
                path.push_back(node -> left);
                paths.push_back(path);
            }
        }
        int pathLength = min(p_path.size(), q_path.size());
        for (int i = 1; i < pathLength; i++) {  // 找p, q路径中最后一个相同的节点
            if (p_path[i] != q_path[i])
                return p_path[i - 1];
        }
        if (p_path[pathLength - 1] == q_path[pathLength - 1]) return p_path[pathLength - 1]; // 路径中最后一个节点相同, 则返回最后一个节点
        return root;
    }
};

卡尔哥的思路:

其实就是通过后序递归, 先找到p, q节点, 如果从左右子树里都找到了p, q, 那么在递归中首先满足这个条件的节点, 一定就是二者的最近公共祖先.

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == q || root == p || !root) return root;   // 如果该节点为空, 或者为p, 或q, 就返回该节点
        TreeNode *left = lowestCommonAncestor(root -> left, p, q);  // 在左子树中找p, q的最近公共祖先
        TreeNode *right = lowestCommonAncestor(root -> right, p, q);// 在右子树中找
        if (left && right) return root; // 左右有p, q的存在, 本节点一定是祖先
        if (left && !right) return left;// 左子树中有目标节点, 返回左子树中的目标节点
        if (!left && right) return right;// 右子树中有目标节点, 返回右子树中的目标节点
        return NULL;
    }
};