LeetCode:二叉搜索树中第K小的数【230】

题目描述

给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明:
你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
  2
输出: 1

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3

进阶:
如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化 kthSmallest 函数?

题目分析

LeetCode:二叉搜索树中第K小的数【230】-LMLPHP

Java题解

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
int count = countNodes(root.left);
if(k<=count)
return kthSmallest(root.left,k);
else if(k>count+1)
return kthSmallest(root.right,k-1-count);
return root.val; } public int countNodes(TreeNode node)
{
if(node ==null)
return 0;
return 1+countNodes(node.left)+countNodes(node.right);
}
}  

DFS——中序递归

 // better keep these two variables in a wrapper class
private static int number = 0;
private static int count = 0; public int kthSmallest(TreeNode root, int k) {
count = k;
helper(root);
return number;
} public void helper(TreeNode n) {
if (n.left != null) helper(n.left);
count--;
if (count == 0) {
number = n.val;
return;
}
if (n.right != null) helper(n.right);
}  

DFS——中序迭代

public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> st = new Stack<>(); while (root != null) {
st.push(root);
root = root.left;
} while (k != 0) {
TreeNode n = st.pop();
k--;
if (k == 0) return n.val;
TreeNode right = n.right;
while (right != null) {
st.push(right);
right = right.left;
}
} return -1; // never hit if k is valid
}
05-11 20:18