day 21|● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

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

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

解：

class Solution {
public:
    //INT_MAX、INT_MIN表示最大最小整数
    int result = INT_MAX;
    TreeNode* pre=NULL;
    void traversal(TreeNode* cur)
    {
        if(cur == NULL) return;
        //左
        traversal(cur->left);
        //中
        if(pre!=NULL)
        {
        if(result > (cur->val)-(pre->val))
            result= (cur->val)-(pre->val);
        }
        pre=cur;
        //右
        traversal(cur->right);
    }
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return result;
    }
};

501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

解：

class Solution {
public:
    int count;
    int maxcount;
    TreeNode* pre=NULL;
    void traversal(TreeNode* cur,vector<int>& vec) {
        if(cur==NULL) return;
        //左
        traversal(cur->left,vec);

        //中
        if(pre == NULL) //第一个节点
        {
            count=1;
        }
        else if(pre->val==cur->val)
        {
            count++;
        }
        else
        {
            count=1;
        }
        pre = cur;

        if(count==maxcount)
        {
            vec.push_back(cur->val);
        }

        if(count>maxcount)
        {
            maxcount = count;
            vec.clear();
            vec.push_back(cur->val);
        }

        //右
        traversal(cur->right,vec);
    }

    vector<int> findMode(TreeNode* root) {
        vector<int> result;
        traversal(root,result);
        return result;
    }
};

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

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

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

解：
遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。
那么二叉树如何可以自底向上查找呢？
回溯啊，二叉树回溯的过程就是从低到上。
后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。
接下来就看如何判断一个节点是节点q和节点p的公共祖先呢。
首先最容易想到的一个情况：如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。

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