wordpress开启会员注册,优化关键词的作用,长沙岳麓区房价新楼盘房价,网站打开的速度特别慢的原因力扣labuladong一刷day34天 文章目录 力扣labuladong一刷day34天一、230. 二叉搜索树中第K小的元素二、538. 把二叉搜索树转换为累加树 一、230. 二叉搜索树中第K小的元素
题目链接#xff1a;https://leetcode.cn/problems/kth-smallest-element-in-a-bst/?utm_sourceLCUShttps://leetcode.cn/problems/kth-smallest-element-in-a-bst/?utm_sourceLCUSutm_mediumip_redirectutm_campaigntransfer2china 思路这是一道很基础的利用二叉搜索树特性的题目中序遍历二叉搜索树就会得到一个递增的序列这个题直接计数相等记录下来即可
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);}
}
