题目链接

牛客网
LeetCode

题目描述

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

   示例1

   输入：
   {5,3,7,2,4,6,8},3
   返回：
   {4}
   按结点数值大小顺序第三小结点的值为4

   示例2

   输入: root = [3,1,4,null,2], k = 1
   3
   / \
   1 4
   \
   2
   输出: 4

   解题思路

   题目一

   利用二叉查找树中序遍历有序的特点。
   先查找左子树，然后判断当前根结点为第几个，然后查找右子树。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot==nullptr) return nullptr;
        inOrder(pRoot,k);
        return ret;
    }
private:
    TreeNode* ret=NULL;
    int cut = 0;
    void inOrder(TreeNode* root, int k){
        if(root==nullptr||cut>=k)
            return;
        inOrder(root->left,k); // 查找左子树
        cut++;    // 访问根结点，当前被访问结点个数加一
        if(cut==k){
            ret = root;
            return;
        }
        inOrder(root->right,k); // 查找右子树
    }
};

题目二

二叉搜索树的 中序遍历倒序 为 递减序列 。
因此，求 “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k 个节点”。
中序遍历的倒序 为 “右、根、左” 顺序，递归法代码如下：

# 打印中序遍历倒序
def dfs(root):
    if not root: return
    dfs(root.right) # 右
    print(root.val) # 根
    dfs(root.left)  # 左

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        if(root==nullptr||k=0)
            return 0;
        inOrder(root,k);
        return ret;
    }
private:
    int cut=0;
    int ret=0;
    void inOrder(TreeNode* root,int k){
        if(root==nullptr)
            return;
        inOrder(root->right,k);
        cut++;
        if(cut==k){
            ret = root->val;
            return;
        }
        inOrder(root->left,k);
    }
};