【Leetcode刷题篇】leetcode230 二叉搜索树中第K小的元素
发布日期:2021-06-29 15:33:27
浏览次数:3
分类:技术文章
本文共 1081 字,大约阅读时间需要 3 分钟。
题目:给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明:
你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。
思路1:递归方式
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; } } // 递归 public int kthSmallest(TreeNode root, int k) { ArrayListres = new ArrayList<>(); res = inorder(root,res); return res.get(k-1); } // 存储 private ArrayList inorder(TreeNode root,ArrayList res){ if(root==null) { return res; } // 左子树 inorder(root.left,res); // 当前节点的值处理 res.add(root.val); // 右子树 inorder(root.right,res); return res; }
思路2:迭代方式
// 迭代 public int kthSmallest_2(TreeNode root, int k) { Stackstack = new Stack<>(); while(true) { while(root!=null) { stack.push(root); root = root.left; } root = stack.pop(); if(--k==0) { return root.val; } root = root.right; } }
转载地址:https://codingchaozhang.blog.csdn.net/article/details/109494694 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月15日 14时54分14秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
解锁宇宙密码:为什么是3、6、9?
2019-04-29
数据可视化中的格式塔心理学
2019-04-29
电动汽车的“专属危险”:网络威胁问题不容小觑
2019-04-29
短暂的告别,马上再回来
2019-04-29
统治50年:为什么SQL在如今仍然很重要?
2019-04-29
测试是一场竞争,而数据每次都会获得胜利
2019-04-29
读心的测谎系统:究竟是骗子还是个天才?
2019-04-29
最大规模技术重建:数据库连接从15000个到100个以下
2019-04-29
复工之后:员工如何改善网络安全?
2019-04-29
70%求职者因此被拒,你还不避开这些“雷区”?!
2019-04-29
办法不在多,有用就行!用Dropout解决过度拟合问题
2019-04-29
色情演员识别?绝对是人脸识别最糟糕的应用……
2019-04-29
让强化学习逃离“乏味区域陷阱”,试着加点噪音吧!
2019-04-29
超详细Spring Boot面试问题集锦,死角一个不留!
2019-04-29
10个业余时间可完成的项目,助你飞速提升编码能力!
2019-04-29
网络爬虫初涉——用python爬取网络小说
2019-04-29
Pycharm+tensorflow dropout 学习(三)
2019-04-29
Pycharm+tensorflow CNN 学习(四)
2019-04-29
用python暴力破解压缩包密码
2019-04-29
基于OpenCV 将图片进行预处理,转变为MNIST图片格式
2019-04-29