题目描述

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

解题思路

1，二叉搜索树的中序遍历是排序的，所以先进行中序遍历得到一个有序list
2，在该list里查找到第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);
    }

}

易错点

一定要注意list和k的边界条件，k不能大于list的size也不能小于等于0