来自Leetcode第230题二叉搜索树中第K小的元素
给定一个二叉搜索树,编写一个函数 kthSmallest
来查找其中第 k 个最小的元素。
说明:
你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
1 2 3 4 5 6 7
| 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 1
|
二叉树中序遍历
通过中序遍历按序保存二叉搜索树中的节点值,最后返回K-1
位置的值即可。
1 2 3 4 5 6 7 8 9 10 11 12 13
| List<Integer> tree = new ArrayList<>(); public int kthSmallest(TreeNode root, int k) { helper(root); return tree.get(k - 1); }
private void helper(TreeNode root){ if(root == null) return; helper(root.left); tree.add(root.val); helper(root.right); }
|
迭代
来源官方题解
在栈的帮助下,可以将方法一的递归转换为迭代,这样可以加快速度,因为这样可以不用遍历整个树,可以在找到答案后停止。
![在这里插入图片描述](/2020/02/13/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%AC%ACK%E5%B0%8F%E7%9A%84%E5%85%83%E7%B4%A0/02/13/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%AC%ACK%E5%B0%8F%E7%9A%84%E5%85%83%E7%B4%A0/25159a5137867644b75f203ee1917645d2cd454d8f4871e371d7edfa67bef083-file_1579413216176.jfif)
1 2 3 4 5 6 7 8 9 10 11 12 13
| public int kthSmallest(TreeNode root, int k) { LinkedList<TreeNode> stack = new LinkedList<>(); while(true){ while(root != null){ stack.add(root); root = root.left; } root = stack.removeLast(); if(--k == 0) return root.val; root = root.right; } }
|
递归
用一个变量记录遍历了的位置,最后返回对应位置的值
1 2 3 4 5 6 7 8 9 10 11 12 13
| int num=0,minimum=0; public int kthSmallest(TreeNode root, int k) { if(root==null)return 0; kthSmallest(root.left,k); num++; if(num==k) { minimum=root.val; return minimum; } kthSmallest(root.right,k); return minimum; }
|