剑指offer_二叉树---二叉搜索树的第k个结点

/**
 * 
 */
package 二叉树;
import java.util.ArrayList;
/**
 * 给定一颗二叉搜索树，请找出其中的第k大的结点。
 * 例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
 */
public class KthNode {
    /**
     * void
     * 
     * @param args
     */
    TreeNode IntKthNode(TreeNode pRoot, int k) {
        if(pRoot==null||k<=0){
            return null;
        }
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        insort(pRoot, list);
        if(k>list.size()){     
            return null;
        }
        return list.get(k - 1);    //中序遍历后把第k个返回
    }
    /**
     * 中序遍历 void
     * 
     * @param args
     */
    public void insort(TreeNode pRoot, ArrayList<TreeNode> list) {
        if (pRoot == null) {
            return;
        }
        insort(pRoot.left, list);
        list.add(pRoot);
        insort(pRoot.right, list);
    }
    public static void main(String[] args) {
        TreeNode pRoot = new TreeNode(5);
         pRoot.left = new TreeNode(3);
         pRoot.right = new TreeNode(7);
         pRoot.left.left = new TreeNode(2);
         pRoot.left.right = new TreeNode(4);
         pRoot.right.left = new TreeNode(6);
         pRoot.right.right = new TreeNode(8);
         KthNode k = new KthNode();
         int a = k.IntKthNode(pRoot, 3).val;
         System.out.println(a);
    }
}