算法:二叉搜索树的第k个结点

二叉搜索树的第k个结点

二叉搜索树的第k个结点

给定一棵二叉搜索树，请找出其中的第k小的结点。

例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

分析

对于二叉树的中序遍历即为有序数列;

所以设置一个index, 对二叉树进行中序遍历;

如果index==k则直接返回;

代码

public class Solution {
    int index = 0;

    TreeNode KthNode(TreeNode root, int k) {
        if (root != null) {
            TreeNode node = KthNode(root.left, k);
            if (node != null)
                return node;
            index++;
            if (index == k)
                return root;
            node = KthNode(root.right, k);
            if (node != null)
                return node;
        }
        return null;
    }
}