题目链接

牛客网

题目描述

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

解题思路

import java.util.*;
public class Solution {
   
    private List<TreeNode> lst = new ArrayList<>();
    private int k;
    public TreeNode KthNode(TreeNode pRoot, int k) {
   
        if (k<=0 || pRoot==null) return null;
        this.k = k;
        addToLst(pRoot);
        return lst.size()>=k? lst.get(k-1): null; // 有可能出现k值大于元素数量
    }
    private void addToLst(TreeNode node) {
   
        if (node==null) return;
        addToLst(node.left);
        lst.add(node);
        if (lst.size()==k) return;
        addToLst(node.right);
    }
}