二叉搜索树的第K大节点题目思路代码总结

168 阅读 0 评论 111 点赞

我是靠谱客的博主淡定台灯，这篇文章主要介绍二叉搜索树的第K大节点题目思路代码总结，现在分享给大家，希望可以做个参考。

题目

给定一棵二叉搜索树，请找出其中第k大的节点。

例如

在如图所示的二叉搜索树中，按节点数值大小排序，第三大节点的值是4.

思路

我们知道，二叉搜索树的中序遍历列表就是排好序的。

所以用二叉树的中序遍历就可以得到它的排序列表。

代码

public static TreeNode getTreeNode(TreeNode t,int k){
    List<TreeNode> list = new ArrayList<>();
    getTreeNodes(t,list);
    return list.get(k - 1);
}
public static void getTreeNodes(TreeNode t,List<TreeNode> ts){
    if(t.left != null)getTreeNodes(t.left,ts);
    ts.add(t);
    if(t.rigth != null)getTreeNodes(t.rigth,ts);
}