代码训练营Day.21 | 530. 二叉搜索树的最小绝对差、501. 二叉搜索树中的众数、236. 二叉树的最近公共祖先

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

1. LeetCode链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2. 题目描述

3. 解法

??????? 中序遍历，记录前一个指针，并记录前一个指针和当前指针的绝对差值。递归。

class Solution {
public:
    TreeNode* pre = NULL;
    int min = INT_MAX;
    void order(TreeNode* root) {
        if (root == NULL) return;
        order(root->left);
        if (pre != NULL && root->val - pre->val < min) {
            min = root->val - pre->val;
        }
        pre = root;
        order(root->right);
    }
    int getMinimumDifference(TreeNode* root) {
        order(root);
        return min;
    }
};

统一迭代

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        TreeNode* pre = NULL;
        int result = INT_MAX;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            TreeNode* cur = st.top();
            if (cur != NULL) {
                st.pop();
                if (cur->right != NULL) st.push(cur->right);
                st.push(cur);
                st.push(NULL);
                if (cur->left != NULL) st.push(cur->left);
            } else {
                st.pop();
                if (pre != NULL && (st.top()->val - pre->val) < result) result = st.top()->val - pre->val;
                pre = st.top();
                st.pop();
            }
        }
        return result;
    }
};

501. 二叉搜索树中的众数

1. LeetCode链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2. 题目描述

3. 解法

中序遍历，记录指针、最大出现频率、当前数字累计个数、最终result。

class Solution {
public:
    TreeNode* pre = NULL;
    int max = 1;
    int count = 1;
    vector<int> result;
    void order(TreeNode* root) {
        if (root == NULL) return;
        order(root->left);
        if (pre != NULL && root->val == pre->val) count++;
        if (pre != NULL && root->val != pre->val) count = 1;
        pre = root;
        if (count > max) {
            result.erase(result.begin(), result.end());
            result.push_back(pre->val);
            max = count;
        } else if (count == max) result.push_back(pre->val);
        order(root->right);
    }
    vector<int> findMode(TreeNode* root) {
        order(root);
        return result;
    }
};

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

1. LeetCode链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2. 题目描述

3. 解法

自己想到的笨办法，自顶向下找，每次都要遍历一遍当前节点之下的节点。很耗时。

class Solution {
public:
    TreeNode* result;
    bool exist(TreeNode* root, TreeNode* p) {
        if (root == NULL) return false;
        if (root == p) return true;
        bool left = exist(root->left, p);
        bool right = exist(root->right, p);
        return left || right;
    }
    void order(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return;
        if (exist(root, p) && exist(root, q)) result = root;
        if (root == p || root == q) return;
        order(root->left, p, q);
        order(root->right, p, q);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        order(root, p, q);
        return result;
    }
};

自底向上递归。就是找到p、q节点。如果，恰好左右节点分别在某节点的左右子树上，直接返回这个节点，即为公共节点。

从下往上遍历，就用后序遍历，先判断完左右子树，然后根据结果判断当前节点。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p || root == q || 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;
    }
};