1. 题目描述
/*
给定一棵二叉搜索树，请找出其中的第k小的结点。
例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
*/
2. 思路
中序遍历二叉搜索树，第K个就是结果
3. 非递归
import java.util.*;
public class Solution {
static TreeNode KthNode(TreeNode pRoot, int k){
return inorderNR(pRoot, k);
}
public static TreeNode inorderNR(TreeNode pRoot, int k){
int count = 0;
Stack<TreeNode> s = new Stack<>();
TreeNode curr = pRoot;
while(curr != null || !s.empty()){
while(curr != null){
s.push(curr);
curr = curr.left;
}
curr = s.pop();
count++;
if(count == k){
break;
}
curr = curr.right;
}
return curr;
}
}4. 递归
import java.util.*;
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k){
return inorderR(pRoot, k);
}
public int count = 0;//注意不能是静态
public TreeNode inorderR(TreeNode root, int k){
if(root != null){
//左
TreeNode left = inorderR(root.left, k);
if(left != null) {return left;}
//中
count ++;
if(count == k) {return root;}
//右
TreeNode right = inorderR(root.right, k);
if(right != null) {return right;}
}
return null;
}
}