Ex54 二叉搜索树的第k大节点

题目描述

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

解题思路

倒着的中序遍历，即“右中左”。

代码

class Solution {
 public:
  int kthLargest(TreeNode *root, int k) { return kth_largest(root, k)->val; }

 private:
  TreeNode *kth_largest(TreeNode *root, int &k) {
    TreeNode *target = nullptr;
    if (root->right != nullptr) target = kth_largest(root->right, k);
    if (target == nullptr) {
      if (k == 1) target = root;
      --k;
    }
    if (target == nullptr && root->left != nullptr)
      target = kth_largest(root->left, k);
    return target;
  }
};

结果

执行结果：通过

执行用时：24 ms, 在所有 C++ 提交中击败了94.79%的用户

内存消耗：24.1 MB, 在所有 C++ 提交中击败了29.22%的用户