给定1颗2叉搜索树，请找出其中的第k大的结点。
中序遍用时候找到第k大结点
import java.util.ArrayList;
public class Solution {
ArrayList<TreeNode> list = new ArrayList<TreeNode>();
TreeNode KthNode(TreeNode pRoot, int k)
{
inorder(pRoot);
if(k<=0 || k> list.size())
return null;
return list.get(k-1);
}
public void inorder(TreeNode root){
if(root == null)
return;
inorder(root.left);
list.add(root);
inorder(root.right);
}
}利用中序遍历，记录遍历结点个数找到第k个结点
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
int count = 0; // 记录遍历结点个数
TreeNode KthNode(TreeNode root, int k)
{
if(root==null|| k<=0)
return null;
TreeNode left = KthNode(root.left,k);
if(left!=null)
return left;
count++;
if(count == k)
return root;
TreeNode right = KthNode(root.right,k);
if(right!=null)
return right;
return null;
}
}
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
