力扣labuladong——一刷day36

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

首先，BST 的特性大家应该都很熟悉了： 1、对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。 2、对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。

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

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Integer> list = new ArrayList<>();public int kthSmallest(TreeNode root, int k) {fun(root);return list.get(k-1);}public void fun(TreeNode root){if(root == null){return ;}fun(root.left);list.add(root.val);fun(root.right);}
}

不使用额外空间

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int res = 0,count = 0;public int kthSmallest(TreeNode root, int k) {fun(root,k);return res;}public void fun(TreeNode root,int k){if(root == null){return ;}fun(root.left,k);count ++;if(count == k){res = root.val;return ;}fun(root.right,k);}
}

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

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int count = 0;public TreeNode convertBST(TreeNode root) {fun(root);return root;}public void fun(TreeNode root){if(root == null){return ;}fun(root.right);count += root.val;root.val = count;fun(root.left);}
}

三、力扣1038. 从二叉搜索树到更大和树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int count = 0;public TreeNode bstToGst(TreeNode root) {fun(root);return root;}public void fun(TreeNode root){if(root == null){return;}fun(root.right);count += root.val;root.val = count;fun(root.left);}
}