列表

详情

230. 二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

 

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

 

 

提示：

 

进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

相似题目

二叉树的中序遍历

二叉树中第二小的节点

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int kthSmallest(TreeNode* root, int k) { } };

golang 解法, 执行用时: 12 ms, 内存消耗: 6.2 MB, 提交时间: 2020-11-20 16:12:00 

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthSmallest(root *TreeNode, k int) int {
    arr := []int{}
    inorder(root, &arr)
    return arr[k-1]
}

func inorder(node *TreeNode, arr *[]int) {
    if node != nil {
        inorder(node.Left, arr)
        *arr = append(*arr, node.Val)
        inorder(node.Right, arr)
    }
    return
}

python3 解法, 执行用时: 64 ms, 内存消耗: 17.5 MB, 提交时间: 2020-11-20 16:01:25 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def inorder(r):
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []
        
        return inorder(root)[k-1]

python3 解法, 执行用时: 100 ms, 内存消耗: 17.4 MB, 提交时间: 2020-11-20 15:39:00 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def gen(r: TreeNode):
            if r:
                yield from gen(r.left)
                yield r.val
                yield from gen(r.right)
        
        it = gen(root)
        for _ in range(k):
            ans = next(it)
        return ans

python3 解法, 执行用时: 60 ms, 内存消耗: 17.3 MB, 提交时间: 2020-11-20 15:29:43 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        # 先排序, 再取ans[k-1]
        ans = [root.val]
        stack = [root.left, root.right]
        while stack:
            node = stack.pop(0)
            if node != None:
                ans.append(node.val)
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)
        ans.sort()
        return ans[k-1]

上一题

© 2024 leetcode.cn