План курса / Все задачи / Алгоритмы и структуры данных
Поиск k-ого наибольшего элемента
средне
Дан корень правильного бинарного дерева поиска root и число k. Нужно вернуть k-ыйнаибольший элемент в дереве (отсчет для k начинается с 1)
ВАЖНО: реализуй обход с использованием рекурсии
Пример 1:
Ввод: root = [10,5,11,-2,7,null,15], k = 2
Вывод: 11
Объяснение: первый наибольший элемент это 15, второй - 11
Пример 2:
Ввод: root = [3,2,4], k = 1
Вывод: 4
Ограничения:
Число узлов в дереве >= 1
1 <= k <= число узлов в дереве
Высота дерева <= 1000
Значение вершин дерева лежит в диапазоне [-10 000, 10 000] (включительно)
/**
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution
{
private static TreeNode Inorder(TreeNode node, ref int k)
{
if (node == null)
{
return null;
}
// идем вправо (обратный in-order)
TreeNode result = Inorder(node.right, ref k);
if (result != null)
{
// если уже нашли k-ую наибольшую
return result;
}
// проверяем k
k -= 1;
if (k == 0)
{
// нашли k-ую наибольшую
return node;
}
// идем влево
return Inorder(node.left, ref k);
}
public static int BiggestBstElement(TreeNode root, int k)
{
TreeNode result = Inorder(root, ref k);
return result.val;
}
}
#include <vector>
using namespace std;
/**
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
TreeNode* inorder(TreeNode* node, int& k) {
if (node == nullptr) {
return nullptr;
}
// идем вправо
TreeNode* result = inorder(node->right, k);
if (result != nullptr) {
// если уже нашли k-ую наименьшую
return result;
}
// проверяем k
k -= 1;
if (k == 0) {
// нашли k-ую наименьшую
return node;
}
// идем влево
return inorder(node->left, k);
}
int biggestBstElement(TreeNode* root, int k) {
TreeNode* result = inorder(root, k);
return result->val;
}
package main
/**
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorder(node *TreeNode, k *int) *TreeNode {
if node == nil {
return nil
}
result := inorder(node.Right, k)
if result != nil {
return result
}
*k -= 1
if (*k == 0) {
return node
}
return inorder(node.Left, k)
}
func biggestBstElement(root *TreeNode , k int) int {
result := inorder(root, &k)
return result.Val
}
import java.util.*;
/**
* class TreeNode {
* Integer val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(Integer val) { this.val = val; }
* TreeNode(Integer val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int index = 0;
private TreeNode inorder(TreeNode node, int k) {
if (node == null) {
return null;
}
// идем вправо
TreeNode result = inorder(node.right, k);
if (result != null) {
// если уже нашли k-ую наименьшую
return result;
}
// проверяем k
index += 1;
if (k == index) {
// нашли k-ую наименьшую
return node;
}
// идем влево
return inorder(node.left, k);
}
public int biggestBstElement(TreeNode root, int k) {
TreeNode result = inorder(root, k);
return result.val;
}
}
from tree_node import TreeNode
# class TreeNode:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def biggest_bst_element(root: TreeNode, k: int) -> int:
def inorder(node: TreeNode) -> int:
if node is None:
return None
result = inorder(node.right)
if result is not None:
return result
nonlocal k
k = k - 1
if k == 0:
return node.val
return inorder(node.left)
return inorder(root)
import { TreeNode } from './treeNode.js';
/**
* class TreeNode {
* constructor(val, left, right) {
* this.val = val;
* this.left = (left === undefined ? null : left);
* this.right = (right === undefined ? null : right);
* }
* }
*/
export function inorder(node, kObj) {
if (node === null) {
return null;
}
// идем вправо (обратный in-order)
const rightResult = inorder(node.right, kObj);
if (rightResult !== null) {
// если уже нашли k-ую наибольшую
return rightResult;
}
// проверяем k
kObj.k -= 1;
if (kObj.k === 0) {
// нашли k-ую наибольшую
return node;
}
// идем влево
return inorder(node.left, kObj);
}
/**
* @param {TreeNode} root
* @param {number} k
* @returns {number}
*/
export function biggestBstElement(root, k) {
const kObj = { k };
const result = inorder(root, kObj);
return result.val;
}
