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

二叉搜索树的性质，中序是有序数组，所以最小绝对值差其实可以转化为相邻元素的差，不开辟数组记录的话，可以用双指针（cur和pre）记录中序遍历输出的上一个节点和这个节点并更新插值，有几个细节注意。

pre是全局变量，这样才能确保递归回退的时候pre没有被回溯，要不旧的节点就丢失了。
pre要判空，要不第一个节点没有pre会报空指针异常。

//C++
class Solution {
public:
    int result = INT_MAX;
    TreeNode* pre;
    int getMinimumDifference(TreeNode* root) {
        doit(root);
        return result;
    }
    void doit(TreeNode* cur) {
        if (cur == nullptr) return;
        doit(cur->left); //左
        if (pre != nullptr) {
            result = min(result, cur->val - pre->val);//中
        }
        pre = cur;
        doit(cur->right);//右
    }
};

开辟数组。

public class Solution {
    List<int> a = new List<int>();
    int result = int.MaxValue;
    public int GetMinimumDifference(TreeNode root) {
        doit(root);
        for (int i = 1; i < a.Count; i++) {
            if (a[i] - a[i - 1] < result) result = a[i] - a[i - 1];
        }
        return result;
    }
    public void doit(TreeNode cur) {
        if (cur == null) return;
        doit(cur.left);
        a.Add(cur.val);
        doit(cur.right);
    }
}

501.二叉搜索树中的众数

如果不是二叉搜索树的话，先map扫一遍记录频率，再转成vector依据频率进行排序，再取前面的最大值即可。二刷写一下C# Dictionary到List再自定义sort cmp函数。

//C++ map法
class Solution {
private:

void searchBST(TreeNode* cur, unordered_map<int, int>& map) { // 前序遍历
    if (cur == NULL) return ;
    map[cur->val]++; // 统计元素频率
    searchBST(cur->left, map);
    searchBST(cur->right, map);
    return ;
}
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second;
}
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> map; // key:元素，value:出现频率
        vector<int> result;
        if (root == NULL) return result;
        searchBST(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp); // 给频率排个序
        result.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {
            // 取最高的放到result数组中
            if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
            else break;
        }
        return result;
    }
};

由于二叉树中序遍历有序，可以用cnt记录连续的元素个数（使用双指针更新，cur=pre, cnt++， cur！=pre, cnt = 1），并动态更新结果数组，有个小技巧就是找到更优的结果就把之前记录的清除掉，这样就不用先遍历记录最大cnt，再遍历一次取出元素了。

双指针避免单独开辟数组记录。
只要当前的cnt超过了已有的最大连续记录，就把val放进去，但一定要把以前的清空并更新cnt。
如果当前cnt等于最大连续记录，把val放进去
注意等于的if判断要放到大于前面，因为大于时会更新cnt，等于的条件也会满足会放两次，或者是两种条件用else if 连接

这个双指针妙的地方主要还是在思想，类似于动态规划的状态转移，并不等到全部遍历完才确定maxCount，而是每次遍历都确定目前已遍历序列的maxCount，因为下次遍历是在目前序列的基础上，所以下次maxCount的状态可以由目前转移过去，总的来说就是一个状态迭代的思想。状态迭代的思想很关键，总是能确定局部最优解，在处理海量数据以及分布式数据时能实时给出局部最优结果，并且有较低的时间复杂度

//C++ cnt动态记录
class Solution {
public:
    vector<int> res;
    int cnt = 0;
    int maxValue = INT_MIN;
    TreeNode* pre = nullptr;
    vector<int> findMode(TreeNode* root) {
        doit(root);
        return res;
    }
    void doit(TreeNode* cur) {
        if (cur == nullptr) return;
        doit(cur->left);
        if(pre == nullptr) {
            cnt = 1;
        } else if (cur->val == pre->val) cnt++;
        else cnt = 1;
        pre = cur;

  		
        if (cnt > maxValue) {
            maxValue = cnt;
            res.clear();
            res.push_back(cur->val);
        } //这里注意，如果 cnt > maxVlaue在前，为了避免取两次结果，要用else连接
        else if (cnt == maxValue) {
            res.push_back(cur->val);
        }  
        doit(cur->right);
        return;
    }
};

C# cnt== maxValue 在前。

public class Solution {
    List<int> result;
    int cnt;
    TreeNode pre;
    int maxValue;
    public int[] FindMode(TreeNode root) {
        cnt = 0;
        maxValue = int.MinValue;
        result = new List<int>();
        pre = null;
        doit(root);
        return result.ToArray();
    }
    public void doit(TreeNode cur) {
        if (cur == null) return;
        doit(cur.left);
        if (pre == null) cnt = 1;
        else if (pre.val == cur.val) cnt++;
        else cnt = 1;
        if (cnt == maxValue) {
            result.Add(cur.val);
        }
        if (cnt > maxValue) {
            maxValue = cnt;
            result.Clear();
            result.Add(cur.val);
        }
        pre = cur;
        doit(cur.right);
        return;
    }
}

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

求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。

alt

在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果，因为right要不然是找到了结果，要不然是其中一个节点所在的分支，往上回溯判断就可以。
有一点需要注意，那就是查询的值肯定存在树中，所以返回的时候如果某个值本身不是最近公共祖先，不会存在到最后只有一边查到了一个元素返回不为null但认为是正确的，因为这种，迟早左右子树的查找结果会碰上都不为null（）。
在相遇之前，cur是p或者q，相遇之后cur就是相遇的最近公共祖先了。
if (cur == nullptr || cur == p || cur == q) return cur; 包含当前节点就是最近公共祖先的情况，此时下面的节点都不用搜索，直接返回就行。

//C++
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return doit(root, p, q);
    }
    TreeNode* doit(TreeNode* cur, TreeNode *p, TreeNode *q) {
        if (cur == nullptr || cur == p || cur == q) return cur;
        TreeNode* left = doit(cur->left, p ,q);
        TreeNode* right = doit(cur->right, p , q);
        if (left != nullptr && right != nullptr) return cur;
        if (left != nullptr && right == nullptr) return left;
        else if (left == nullptr && right != nullptr) return right;
        else return nullptr; 
    }
};

判断条件可以进一步简化，使用left==nullptr return right就可以涵盖左为空，右不为空和左为空，右为空的情况,而不是 right != nullptr return right 只能涵盖right不为空，左为空的情况（左不为空，右不为空已经在上面考虑过了），应该从左指针为空，反过来返回右指针入手优化，和day20。合并二叉树是一个思路，太妙了。

//C#
public class Solution {
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return doit(root, p, q);
    }
    public TreeNode doit(TreeNode cur, TreeNode p, TreeNode q) {
        if (cur == null || cur == p || cur == q) return cur;
        TreeNode left = doit(cur.left, p, q);
        TreeNode right = doit(cur.right, p, q);
        if (left != null && right != null) return cur;
        if (left == null) return right;
        else return left;
    }
}

[代码随想录一刷] day21 二叉树

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

501.二叉搜索树中的众数

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