给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
import java.util.ArrayList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
/**
* 给定一棵二叉搜索树,请找出其中的第k小的结点。
* 例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
* 中序遍历一下,变成 小 中 大,然后找出第k小的数
*/
TreeNode KthNode(TreeNode pRoot, int k)
{
if (k <= 0) {
return null;
}
ArrayList<TreeNode> resultLists = new ArrayList<>();
inOrder(pRoot, resultLists, k);
if (k > resultLists.size()) {
return null;
}
return resultLists.get(k - 1);
}
public void inOrder(TreeNode root, ArrayList<TreeNode> resultLists, int k) {
if (resultLists.size() >= k) {
return;
}
if (root != null) {
inOrder(root.left, resultLists, k);
resultLists.add(root);
inOrder(root.right, resultLists, k);
}
}
}
最后
以上就是难过红牛最近收集整理的关于二叉搜索树的第k个结点 java的全部内容,更多相关二叉搜索树的第k个结点内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复