二叉搜索树的第k个结点

Posted on

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
List<TreeNode> mList = new ArrayList<>();

TreeNode KthNode(TreeNode pRoot, int k) {
    // 先序遍历找到二叉搜索树增序数列
    preNode(pRoot);
    for (int i = 1; i <= mList.size(); i++) {
        if (i == k) {
            return mList.get(i - 1);
        }
    }
    return null;
}


public void preNode(TreeNode pRoot) {
    if (pRoot == null) {
        return;
    }
    if (pRoot.left != null) {
        preNode(pRoot.left);
    }
    mList.add(pRoot);
    if (pRoot.right != null) {
        preNode(pRoot.right);
    }
}