leetcode_day21

今日任务：

• 530. 二叉搜索树的最小绝对差easy
• 501. 二叉搜索树中的众数easy
• 236. 二叉搜索树的最近公共祖先medium

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

题目：（仅题干，示例请移步力扣）

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

思路：

由于是二叉搜索树，时刻牢记中序遍历二叉搜索树相当于遍历有序数组，所以大思路就是中序遍历树，并维护一个最小绝对差

中序遍历这里采用递归法，递归途中需要记录上一个节点的值以求出两数之差

class Solution {
public:
    void traversal(TreeNode * root, int &ans, int & pre) {
        if(root) {
            traversal(root->left, ans, pre);
            if(pre == -1) pre = root->val;
            else {
                ans = min(ans, root->val - pre);
                pre = root->val;
            }
            traversal(root->right, ans, pre);
        }
    }
    int getMinimumDifference(TreeNode* root) {
        int ans = INT_MAX, pre = -1;
        traversal(root, ans, pre);
        return ans;
    }
};

501. 二叉搜索树中的众数

题目：

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

思路：

大思路仍然依靠中序遍历二叉搜索树相当于遍历有序数组，问题转换为求出一个有序数组中的众数，那么在遍历时记录每个数的频率，维护一个最大频率

若该数最后的频率小于最大频率，则不做操作；等于最大频率，则加入答案中；大于最大频率，则更新最大频率，清空当前答案，并将当前数加入答案

依然是递归中序遍历

class Solution {
public:
    vector<int> ans;//答案answer
    int max_freq = 0;//最大频率
    void dfs(TreeNode * root, int &cur, int &freq) {
        if(root == nullptr) return;
        dfs(root->left, cur, freq);//中序左
        if(root->val == cur) {//当前数cur还未遍历完，继续加频率freq
            freq++;
            if(max_freq == freq) {//如果已经赶上最大频率，加入答案
                ans.push_back(cur);
            }
            else if(max_freq < freq) {//如果已经超过，更新max，清空答案，重新加入cur作为答案
                max_freq = freq;
                ans.clear();
                ans.push_back(cur);
            }
        }
        else{
            cur = root->val;//当前数cur遍历结束，将cur更新为新的数，频率重置
            freq = 1;
        }
        dfs(root->right, cur, freq);
    }
    vector<int> findMode(TreeNode* root) {
        int cur = root->val, freq = 0;
        dfs(root, cur, freq);
        return ans;
    }
};

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

题目：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路

初次尝试越想越复杂，以失败告终，原因是单次递归逻辑和终止条件没想明白，

按照carl的递归三部曲：

1. 确定递归返回值和参数。这一步没问题，就按照力扣给的核心方法的定义就可以，返回公共祖先的指针，参数就是两个节点p、q和根节点
2. 确定递归终止条件。第一个终止条件想到了：“root等于p或者q时，或者root为空”就返回root。之后就开始混乱了，尝试讨论p、q是root的孩子还是孙子还是更远的孩子，遂失败
3. 确定单次递归逻辑。失败

我没有分析出：当递归到 最近公共祖先的祖先时，返回值也应该是最近公共祖先，也就是说最近公共祖先是会不断向上传递的，这样就就能保证最近而不会得到深度更浅的公共祖先。

对于遍历一条路还是遍历整棵树，carl老师的解释令我耳目一新：

在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。

搜索一条边的写法：

if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;

搜索整个树写法：

left = 递归函数(root->left);  // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理;         // 中 

由于返回值确定，所以递归时肯定会有东西接住返回值，又由于，递归的参数是root，返回值也是root，所以当递归root左右孩子时，返回值也应该是左右孩子，即必然会有

left = lowestCommonAncestor(root->left, p, q);

由于这道题不需要对树进行操作，只需要查找遍历，所以left并不是root->left，即不需要更新。根据carl的区分，我们可以根据这条语句推断我们之后应该进行left和right的逻辑处理，那么就可以合理推测应该判断left和right是否为空，因为如果没有找到必定返回空，而找到p、q才会返回p或者q，那么如果left和right都返回了，就遇到答案（root）了，向上不断返回即可。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q || root == nullptr) return root;

        TreeNode * left = lowestCommonAncestor(root->left, p, q);
        TreeNode * right = lowestCommonAncestor(root->right, p, q);

        if(left == nullptr && right == nullptr) 
            return nullptr;
        else if(left == nullptr && right != nullptr) 
            return right;
        else if(left != nullptr && right == nullptr)
            return left;
        else 
            return root;
    }
};

对于想了半小时还WA的我来说，这真是段优雅的代码