力扣labuladong一刷day34天

力扣labuladong一刷day34天

一、230. 二叉搜索树中第K小的元素

题目链接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
思路：这是一道很基础的利用二叉搜索树特性的题目，中序遍历二叉搜索树就会得到一个递增的序列，这个题直接计数相等记录下来即可

class Solution {
   int i = 1, value = 0;
    public int kthSmallest(TreeNode root, int k) {
        traverse(root, k);
        return value;
    }

    void traverse(TreeNode root, int k) {
        if (root == null) return;
        traverse(root.left, k);
        if (i == k) {
            value = root.val;
        }
        i++;
        traverse(root.right, k);   
    }
}

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

题目链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/
思路：本题让把二叉搜索树变成累加树，每个节点的值变成大于他的值与他的和，那这样做的话，中序遍历最后的位置的一个数是最大的，也就是他自身，倒数第二个数是自身值与倒数第一的和，这样我们只需要把中序遍历的顺序颠倒一下，先遍历right再遍历left，然后用一个p指针记录上一个遍历过的节点，这样就可以完成累加。

class Solution {
   TreeNode p = null;
    public TreeNode convertBST(TreeNode root) {
        traverse(root);
        return root;
    }
    
    void traverse(TreeNode root) {
        if (root == null) return;
        traverse(root.right);
        if (p == null) {
            p = root;
        }else {
            root.val += p.val;
            p = root;
        }
        traverse(root.left);
    }
}