题意：给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

解题思路

解法1：
1.二叉搜索树的中序遍历结果为有序链表
2.降序排序list，然后返回第k-1个节点值

解法2

1.中序遍历结果为有序链表，结果求取的是第k个大数，也就是，中序遍历的倒叙结果的第k个节点的值
2.在中序遍历过程中，将左右节点的先后顺序变换一下，即为倒序结果

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

class Solution {
    public int kthLargest(TreeNode root, int k) {
        midle(root);
        Collections.sort(list, new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        return list.get(k - 1);
    }
    LinkedList<Integer> list = new LinkedList<Integer>();
    private void midle(TreeNode root) {
        if (root == null) {
            return;
        }

        midle(root.left);
        list.add(root.val);
        midle(root.right);
    }

    class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int _val) {
            val = _val;
        }

        public TreeNode(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }
}

##解法2
class Solution {
    int k, ans;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        // 中序遍历结果为有序链表，结果求取的是第k个大数，也就是，中序遍历的倒叙结果的第k个节点的值
        // 在中序遍历过程中，将左右节点的先后顺序变换一下，即为倒序结果
        middle(root);
        return ans;
    }

    private void middle(TreeNode root) {
        if (root == null) {
            return;
        }
        middle(root.right);
        if (k == 0) {
            return;
        }
        k--;
        if (k == 0) {
            ans = root.val;
        }
        middle(root.left);
    }

}