【算法训练营day21】LeetCode530.二叉搜索树的最小绝对差 LeetCode501. 二叉搜索树中的众数 LeetCode236. 二叉树的最近公共祖先

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

题目链接：530.二叉搜索树的最小绝对差

初次尝试

利用二叉搜索树的性质：中序遍历的结果是有序递增数组，最后遍历该数组得到最小绝对差。

class Solution {
public:
    vector<int> vec;
    void traversal(TreeNode* node) {
        if (!node) return;
        traversal(node -> left);
        vec.push_back(node -> val);
        traversal(node -> right);
    }

    int getMinimumDifference(TreeNode* root) {
        int min_diff = INT_MAX;
        traversal(root);
        for (int i = 0; i < vec.size() - 1; i++) {
            min_diff = min(min_diff, vec[i+1] - vec[i]);
        }
        return min_diff;
    }
};

看完代码随想录后的想法

有想过在中序遍历过程中就计算最小绝对差，但是没有成功实现，题解是通过设置一个记录前一个节点的指针实现的，代码如下：

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;
    }
};

LeetCode501. 二叉搜索树中的众数

题目链接：501. 二叉搜索树中的众数

初次尝试

只能想到把二叉搜索树转化为有序数组的方法，而且实现起来比较生疏，没有成功。

看完代码随想录后的想法

和上一题一样，利用的是双指针，对递归中的各种情况进行了讨论，需要好好想一想才能成功实现的方法。

class Solution {
public:
    int count = 0;
    int max_count = 0;
    TreeNode* pre = NULL;
    vector<int> ans;
    void traversal(TreeNode* node) {
        if (node == NULL) return;
        traversal(node -> left);

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

        pre = node;

        if (count == max_count) {
            ans.push_back(node -> val);
        }
        else if (count > max_count) {
            max_count = count;
            ans.clear();
            ans.push_back(node -> val);
        }

        traversal(node -> right);
        return;
    }

    vector<int> findMode(TreeNode* root) {
        count = 0;
        max_count = 0;
        pre = NULL;
        ans.clear();
        
        traversal(root);
        return ans;
    }
};

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

题目链接：236. 二叉树的最近公共祖先

初次尝试

后序递归法，递归处理逻辑为左右子树中是否包含目标节点，如果包含两个，则当前节点即为所求；如果包含一个，判断当前节点是否为目标节点之一，如果是，则当前节点即为所求，如果不是，则返回true继续寻找另一个目标节点；如果一个都不包含，则判断当前节点是否是目标节点，是返回true，不是返回false继续寻找。

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

看完代码随想录后的想法

题解的思路更加简单，把bool等价转化为返回节点空or不空，并且在递归单层逻辑处理上也有优化。

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;
        }

    }
};