阿里云搭建公司网站,国外门户网站设计,郑州做网站优化,前端开发是做网站的吗提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣230. 二叉搜索树中第K小的元素二、力扣538. 把二叉搜索树转换为累加树三、力扣1038. 从二叉搜索树到更大和树 前言 首先#xff0c;BST 的特性大家应该… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣230. 二叉搜索树中第K小的元素二、力扣538. 把二叉搜索树转换为累加树三、力扣1038. 从二叉搜索树到更大和树 前言 首先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 {ListInteger 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);}
}
