运营网站是多少网络销售是做什么的
题目
- 二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
提示：
树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104
解决思路
解决方法
方法一：
//完全可以先放后取//而不是边取边放//代码好些 逻辑也容易理解fun kthSmallest2(root: TreeNode?, k: Int): Int {val linkedList = LinkedList<TreeNode>()var cur: TreeNode? = rootvar curIndex = 1while (!linkedList.isEmpty() || cur != null) {while (cur != null) {linkedList.push(cur)cur = cur.left}cur = linkedList.pop()if (curIndex++ == k) {return cur!!.`val`}//当前节点不满足 移出去cur = cur?.right}return -1}
方法二：
我自己手写的，逻辑不是很清晰
队列的push 和 pop 不太好
public fun kthSmallest(root: TreeNode?, k: Int): Int {val linkedList = LinkedList<TreeNode>()var cur: TreeNode? = nullif (root != null) {linkedList.add(root)}var curIndex = 1while (!linkedList.isEmpty()) {//当前cur为空 说明有一个新的根节点 需要遍历左孩子if (cur == null) {cur = linkedList.peek()while (cur?.left != null) {linkedList.push(cur.left)cur = cur.left}} else {cur = linkedList.peek()}if (curIndex++ == k) {return cur!!.`val`}//当前节点不满足 移出去linkedList.pop()//右边有孩子 那么需要遍历左孩子if (cur?.right != null) {linkedList.push(cur.right)cur = null}}return -1}
总结
按部就班就可以做好95%的工作 所以机器有时候比人做的更好 更快 不管是ETC 不管是围棋
大部分还都是平凡人
有的时候需要忘的差不多了才去些算法才能记忆深刻
做题频率确实低了很多