题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
题目来源：剑指Offer
- 思路
从二叉搜索树中找第k小节点等价于将此树按中序排序后找第k个节点。
非递归实现
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k) {
if(pRoot == null || k <= 0)
return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
int num = 0;
TreeNode root = pRoot; //为了不破坏原来的节点，也可以不加
while(root != null || stack.isEmpty() == false){
while(root != null){
stack.push(root);
root = root.left;
}
TreeNode node = stack.pop();
num ++;
if(num == k)
return node;
root = node.right;
}
return null;
}
}
递归实现
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
int cnt = 0;
TreeNode KthNode(TreeNode pRoot, int k) {
if(pRoot == null || k <= 0)
return null;
TreeNode node = KthNode(pRoot.left, k);
if(node != null)
return node;
cnt ++;
if(cnt == k)
return pRoot;
node = KthNode(pRoot.right, k);
if(node != null)
return node;
return null;
}
}
其中 if(node != null)return node; 的作用是把在下层递归中找到的结果返回最顶层（如果node为空则表示还没有找到符合要求的节点，需要往下判断接着找，反之则为找到了）；如果不加的话最终找到的结果只会返回到当前递归的上一个递归中，最后无法传递到最顶层
