剑指Offer——二叉搜索树的第k个结点

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

思路:利用二叉树的中序遍历,遍历到第K个节点时即可。

代码:

public class Solution{
    private TreeNode ret;
    private int cnt = 0;

    public TreeNode KthNode(TreeNode pRoot, int k) {
        inOrder(pRoot, k);
        return ret;
    }

    private void inOrder(TreeNode root, int k) {
        if (root == null || cnt >= k)
            return;
        inOrder(root.left, k);
        cnt++;
        if (cnt == k)
            ret = root;
        inOrder(root.right, k);
    }
}

 

上一篇:94 - Binary Tree Inorder Traversal


下一篇:Binary Tree Inorder Traversal