题解 | #二叉搜索树的第k个节点#

方法一：非递归

1. 先用队列对二叉树进行层次遍历，依次将各个节点的值存放到数组中
2. 接着对该数组进行排序，因为数组是从0开始的，所以返回第k-1个元素

注意一些需要返回-1的情况：树的根节点为空；k==0;k>n

public class Solution {

public int KthNode (TreeNode proot, int k) {
    // write code here
    if(proot==null)
        return -1;
    ArrayList<Integer> arr = new ArrayList<>();
    ArrayDeque<TreeNode> dq = new ArrayDeque<>();
    dq.addLast(proot);
    while(!dq.isEmpty()){
        int curSize = dq.size();
        while(curSize-->0){
            TreeNode node = dq.pollFirst();
            arr.add(node.val);
            if(node.left!=null) dq.addLast(node.left);
            if(node.right!=null) dq.addLast(node.right);
        }
    }
    if(k>arr.size() || k==0)
        return -1;
    Collections.sort(arr);
    return arr.get(k-1);
}

}

方法二：递归方式

public class Solution {

public int KthNode (TreeNode proot, int k) {
    if(proot==null || k<=0){
        return -1;
    }
    //list集合用来存储二叉搜索树中序遍历的结果
    ArrayList<Integer>  list=new  ArrayList<Integer>();
    dfs(proot,list);
    if(k>list.size())
        return -1;
    //返回集合中第k个元素,数组从0开始所以是k-1
    return list.get(k-1);
}
//中序遍历
public void dfs(TreeNode proot,ArrayList<Integer> list){
    if(proot==null)
        return;
    dfs(proot.left,list);
    list.add(proot.val);
    dfs(proot.right,list);
}

}