import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author wuze
 * @desc ...
 * @date 2021-03-22 13:39:48
 */
public class 二叉搜索树的第k大节点_剑指offer_54 {

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }

 /*
 思路：
 1、先遍历整颗树，将节点值都放在list里面
 2、遍历list，加入数组arr（使用for循环）
 3、对arr排序（Arrays.sort(arr);）
 4、取出第k大元素（arr[arr.length-k];）
  */

    class Solution {
        /*

        补充：
        arr.length
        arrayList.size()
        str.length()

        */
        public int kthLargest(TreeNode root, int k) {
            ArrayList<Integer> list = new ArrayList<>();
            dfs(root,list);
            int arr[]= new int[list.size()];
            for(int i=0;i<list.size();i++){
                arr[i]=list.get(i);
            }
            Arrays.sort(arr);
            return arr[arr.length-k];
        }


        void dfs(TreeNode root, ArrayList<Integer> list){
            if(root==null){
                return ;
            }
            //左中右 ==> 中序遍历
            dfs(root.left,list);
            list.add(root.val);
            dfs(root.right,list);
        }
    }

}