給定1顆2叉搜索樹，請找出其中的第k大的結(jié)點(diǎn)。
中序遍用時候找到第k大結(jié)點(diǎn)
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);
}
}利用中序遍歷，記錄遍歷結(jié)點(diǎn)個數(shù)找到第k個結(jié)點(diǎn)
/*
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; // 記錄遍歷結(jié)點(diǎn)個數(shù)
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網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
