专栏首页计算机视觉与深度学习基础Leetcode 230. Kth Smallest Element in a BST

Leetcode 230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:  You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

找出二叉搜索树上第k大的数。

通常我们可以遍历一下,然后得到一个排序好的容器,直接在这个容器上查询就可以了,

但是这题说可能会经常对树进行插入和删除操作,这使得排序结果会经常变化,所以我们用中序遍历来实现。

/**
 * 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:
    void dfs(TreeNode* root, int &k, int &res)
    {
        if(!root) return ;
        dfs(root->left, k, res);
        k--;
        if(!k) 
        {
            res = root->val;
            return ;
        }
        dfs(root->right, k, res);
    }
    int kthSmallest(TreeNode* root, int k) {
        int res;
        dfs(root, k, res);
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 110 Balanced Binary Tree

    Given a binary tree, determine if it is height-balanced. For this problem, a h...

    triplebee
  • Leetcode 144 Binary Tree Preorder Traversal

    Given a binary tree, return the preorder traversal of its nodes' values. For e...

    triplebee
  • Leetcode 145 Binary Tree Postorder Traversal

    Given a binary tree, return the postorder traversal of its nodes' values. For ...

    triplebee
  • Leetcode 110 Balanced Binary Tree

    Given a binary tree, determine if it is height-balanced. For this problem, a h...

    triplebee
  • Leetcode 145 Binary Tree Postorder Traversal

    Given a binary tree, return the postorder traversal of its nodes' values. For ...

    triplebee
  • Leetcode 144 Binary Tree Preorder Traversal

    Given a binary tree, return the preorder traversal of its nodes' values. For e...

    triplebee
  • 【leetcode刷题】T130-二叉搜索树中第K小的元素

    https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

    木又AI帮
  • 算法篇:树之倒数k个节点

    这类题目的核心思想是,利用二叉树的中序遍历是从小到大的,将其转变成数组,然后对这个有序数组进行取值操作就可以了。

    灰子学技术
  • 算法篇:树之树的层次遍历

    树的层次遍历是树的基本操作之一,包括二叉树的层次遍历,多叉树的层次遍历,以及二叉树层次遍历的变形题目,层次遍历+每一层的节点的翻转等操作。

    灰子学技术
  • LintCode 二叉树的最小深度题目代码

    desperate633

扫码关注云+社区

领取腾讯云代金券