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

中序遍历解决树中top K问题

本题就直接用递归来做了

public class Solution {
//为什么可以直接获取list中的第k-1个节点，就是所需节点？
//题目已经告诉这是一棵二叉搜索树，所以是有序的（根节点的值大于左子树，小于右子树）
//在中序遍历中二叉搜索树的遍历结果是从小到大的，也即升序输出
//所以，获取list中第k-1个元素即为所需元素节点
    List<TreeNode> list = new ArrayList<>();
    TreeNode KthNode(TreeNode pRoot, int k) {
        inorderDfs(pRoot);
        if(pRoot == null || k == 0 || k > list.size()) return null;
        return list.get(k-1);
    }
    public void inorderDfs(TreeNode root){
        if(root == null) return;
        inorderDfs(root.left);
        list.add(root);
        inorderDfs(root.right);
    }


}