给定一棵二叉搜索树,找出其中的第k小的结点。例如(5,3,7,2,4,6,8)中,按结点数值大小顺序第3小的结点值为4。
import java.util.Stack;
public class T_62_KthNode {
int count = 0;
//递归,中序遍历
TreeNode KthNode(TreeNode pRoot, int k) {
if (pRoot != null) {
TreeNode node = KthNode(pRoot.left, k);
if (node != null) {
return node;
}
count++;
if (count == k) {
return pRoot;
}
node = KthNode(pRoot.right, k);
if (node != null) {
return node;
}
}
return null;
}
//非递归,中序遍历
TreeNode KthNode2(TreeNode pRoot, int k) {
if (pRoot != null) {
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || pRoot != null) {
if (pRoot != null) {
stack.push(pRoot);
pRoot = pRoot.left;
} else {
pRoot = stack.pop();
count++;
if (count == k) {
return pRoot;
}
pRoot = pRoot.right;
}
}
}
return null;
}
}
最后
以上就是甜美流沙最近收集整理的关于剑指offer——第62题:二叉搜索树的第k小的结点的全部内容,更多相关剑指offer——第62题:二叉搜索树内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复