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

文档链接：https://programmercarl.com/

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

题目链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/

思路：二叉搜索树记得使用中序遍历最方便！

注意是二叉搜索树，二叉搜索树可是有序的。

遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。

双指针法：

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

LeetCode501.二叉搜索树中的众数

题目链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/

思路：自己体会吧

双指针法：

class Solution {
public:
    TreeNode* pre = NULL;
    vector<int> result;
    int count = 0;
    int maxCount = 0;
    void traversal(TreeNode* cur) {
        if(cur == NULL) return ;
        traversal(cur->left);
        if(pre == NULL) count = 1;
        else if(pre->val == cur->val) count++;
        else if(pre->val != cur->val) count = 1;
        pre = cur;
        if(count == maxCount) result.push_back(cur->val);
        if(count > maxCount) {
            maxCount = count;
            result.clear();
            result.push_back(cur->val);
        }
        traversal(cur->right);
    }
    vector<int> findMode(TreeNode* root) {
        traversal(root);
        return result;
    }
};

双指针法：

int removeElement(int* nums, int numsSize, int val) {
    int fast = 0;
    int slow = 0;
    for(; fast < numsSize; fast++) {
        if(nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

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

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

思路：遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。

后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。

接下来就看如何判断一个节点是节点q和节点p的公共祖先呢。

首先最容易想到的一个情况：如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。

判断逻辑是 如果递归遍历遇到q，就将q返回，遇到p 就将p返回，那么如果 左右子树的返回值都不为空，说明此时的中节点，一定是q 和p 的最近祖先。

后序遍历：

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

总结：二叉搜索树与中序遍历有关，就相当于一个递增的数组。关于自底向上查找，要想得到用后序遍历（左右中）去处理会更加容易。