力扣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);
}
}
