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