leetcode BST遍历递归问题模式小结

writer：lIcht                      email：lIcht.gzl@gmail.com                 date:  2019.11.15

        最近刷力扣碰到三个BST类递归问题，虽然都是简单类型，但是这三道题对BST递归问题都以同一种模式解决，可以为以后碰到的同类BST遍历问题提供参考。

       遍历处理思路：由于力扣题目的出口入口问题，在答题模版的主函数之外创建无返回值的函数专门处理BST遍历处理数据过程更加方便，主函数内只需声明额外需要的变量和调用处理函数就行了。处理函数中主要分为三部分：即需要遍历的顺序以及每一步递归所需要处理的过程。

题目:

1、501. 二叉搜索树中的众数

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        TreeNode* pre = NULL;
        int curTimes=1, maxTimes=0;
        inOrder(root, pre, curTimes, maxTimes, res);
        return res;
    }
    
void inOrder(TreeNode* root, TreeNode*& pre, int& curTimes, int& maxTimes, vector<int>& res){
    if (!root) return;
    inOrder(root->left, pre, curTimes, maxTimes, res);
    if (pre)
        curTimes = (root->val == pre->val) ? curTimes + 1 : 1;
    if (curTimes == maxTimes)
        res.push_back(root->val);
    else if (curTimes > maxTimes){
        res.clear();
        res.push_back(root->val);
        maxTimes = curTimes;
    }
    pre = root;
    inOrder(root->right, pre, curTimes, maxTimes, res);
}
};

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> val_list;
        int res=INT_MAX;
        minval(root, res, val_list);
        return res;
    }
    
void minval(TreeNode* root, int& res, vector<int>& val_list){
    if (!root) return;
    minval(root->left, res, val_list);
    for(auto i: val_list){
        if (abs(root->val-i)<res){
            res = root->val-i;
        }
    }
    val_list.push_back(root->val);
    minval(root->right, res, val_list);
}
};

3、538. 把二叉搜索树转换为累加树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int sum=0;
        travl(root,sum);
        return root;
    }
    void travl(TreeNode* root,int &sum)
    {
        if(root==0)return ;
        travl(root->right,sum);
        sum+=root->val;
        root->val=sum;
        travl(root->left,sum);        
    }
};