給定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 程序員人生 版權所有
