【Leetcode刷题篇】leetcode230 二叉搜索树中第K小的元素
发布日期:2021-06-29 15:33:27
浏览次数:2
分类:技术文章
本文共 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月29日 06时40分20秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
单片机里面的CPU使用率是什么鬼?
2019-04-29
推荐一个优质Linux技术公众号-作者都是一线Linux代码贡献者们哦
2019-04-29
RT-Thread 编程风格指南
2019-04-29
95后高校电子教师,软硬兼修有趣有料!
2019-04-29
使用 STM32 通用 Bootloader ,让 OTA 更加 Easy
2019-04-29
Cache 的基本概念与工作原理
2019-04-29
Android程序员必备!面试一路绿灯Offer拿到手软,Android面试题及解析
2019-04-29
Android程序员的春天!12个View绘制流程高频面试题,分享PDF高清版
2019-04-29
深入浅出Android开发!你会的还只有初级工程师的技术吗?一线互联网公司面经总结
2019-04-29
深度剖析原理!超全Android中高级面试复习大纲,含BATJM大厂
2019-04-29
温故而知新!Android开发者该学习哪些东西提高竞争力?成功入职阿里
2019-04-29
火爆知乎的Android面试题-Android-App的设计架构经验谈,大厂内部资料
2019-04-29
看完直接怼产品经理!Android多进程从头讲到尾,跳槽薪资翻倍
2019-04-29
快速从入门到精通!面试的时候突然遇到答不上的问题怎么办?已拿到offer
2019-04-29
Android开发知识体系!腾讯+字节+阿里面经真题汇总,成功入职阿里
2019-04-29
android开发语言!大厂经典高频面试题体系化集合,移动架构师成长路线
2019-04-29
typescript学习(进阶)
2019-04-29