• 一、题目
  • 二、解题思路
  • 三、解题代码

    一、题目

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

    二、解题思路

    如果按照中序遍历的顺序遍历一棵二叉搜索树,遍历序列的数值是递增排序的。只需要用中序遍历算法遍历一棵二叉搜索树,就很容易找出它的第k大结点。

    三、解题代码

    1. public class Test {
    2. private static class BinaryTreeNode {
    3. private int val;
    4. private BinaryTreeNode left;
    5. private BinaryTreeNode right;
    6. public BinaryTreeNode() {
    7. }
    8. public BinaryTreeNode(int val) {
    9. this.val = val;
    10. }
    11. @Override
    12. public String toString() {
    13. return val + "";
    14. }
    15. }
    16. public static BinaryTreeNode kthNode(BinaryTreeNode root, int k) {
    17. if (root == null || k < 1) {
    18. return null;
    19. }
    20. int[] tmp = {k};
    21. return kthNodeCore(root, tmp);
    22. }
    23. private static BinaryTreeNode kthNodeCore(BinaryTreeNode root, int[] k) {
    24. BinaryTreeNode result = null;
    25. // 先成左子树中找
    26. if (root.left != null) {
    27. result = kthNodeCore(root.left, k);
    28. }
    29. // 如果在左子树中没有找到
    30. if (result == null) {
    31. // 说明当前的根结点是所要找的结点
    32. if(k[0] == 1) {
    33. result = root;
    34. } else {
    35. // 当前的根结点不是要找的结点,但是已经找过了,所以计数器减一
    36. k[0]--;
    37. }
    38. }
    39. // 根结点以及根结点的左子树都没有找到,则找其右子树
    40. if (result == null && root.right != null) {
    41. result = kthNodeCore(root.right, k);
    42. }
    43. return result;
    44. }
    45. }