Leetcode 230. 二叉搜索树中第K小的元素 kth-smallest-element-in-a-bst&& 538. 把二叉搜索树转换为累加树 convert-bst-to-greater-

思路：labuladong

二叉搜索树中序遍历为有序数组，利用该特性进行中序遍历，并在遍历时记录rank值，当rank等于k时输出val

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        traverse(root,k);
        return ret;
    }
    void traverse(TreeNode* root, int k){
        if(root==nullptr) return;
        traverse(root->left,k);
        rank++;
        if(rank==k){
            ret=root->val;
            return;
        } 
        traverse(root->right,k);
    }
    int rank=0;
    int ret=0;
};

题目：

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node * 的新值等于原树中大于或等于 node.val 的值之和。 * * 提醒一下，二叉搜索树满足下列约束条件： * * * 节点的左子树仅包含键 小于 节点键的节点。 * 节点的右子树仅包含键 大于 节点键的节点。 * 左右子树也必须是二叉搜索树。 * * * 注意：本题和 1038: * https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ * 相同   * * 示例 1： * 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] * 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8] * * * 示例 2： * * 输入：root = [0,null,1] * 输出：[1,null,1] * * * 示例 3： * * 输入：root = [1,0,2] * 输出：[3,3,2] * * * 示例 4： * * 输入：root = [3,2,4,1] * 输出：[7,9,4,10]   * 提示： * * * 树中的节点数介于 0 和 10^4^ 之间。 * 每个节点的值介于 -10^4 和 10^4 之间。 * 树中的所有值 互不相同 。 * 给定的树为二叉搜索树。   思路 labuladong： 正向中序遍历为从小到大，那么倒向中序遍历就是从大到小。此时累加遍历值并赋值给该节点，就可得到累加数。 注意先traverse(root->right)再left  

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        traverse(root);
        return root;
    }
    int sum=0;
    TreeNode* traverse(TreeNode* root){
        if(root==nullptr){
            return root;
        }
        traverse(root->right);
        sum+=root->val;
        root->val=sum;
        traverse(root->left);
        return root;
    }
};