Найти k-й наименьший узел в бинарном дереве поиска - PullRequest
Новая
       10

Найти k-й наименьший узел в бинарном дереве поиска

0 голосов
/ 27 октября 2018 
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int cnt = 0;
        int val = -1000;
        int res  = inorderTraversal(root,k,cnt,val);
        return res;
    }


    public int inorderTraversal(TreeNode root,int k,int cnt,int val){

         if (root == null) 
            return val; 

        inorderTraversal(root.left,k,cnt,val);
        cnt++;
        //System.out.println(root.val);
        if(cnt == k){
            //System.out.println(root.val);
            val = root.val;
            return val;
        }
        inorderTraversal(root.right,k,cnt,val);
        return val;
    }
}

Итак, я понял, что могу использовать inorder traversal, чтобы найти k-й наименьший узел.Я не могу понять, как только я найду его, как мне отправить его обратно в нижний стек рекурсии.Я не могу получить ответ здесь.

Примечание. Это не домашняя работа или какое-либо задание.Я смущен рекурсией и пытаюсь понять подход

Questiun из https://leetcode.com/problems/kth-smallest-element-in-a-bst/

1 Ответ

0 голосов
/ 28 октября 2018

На самом деле вы можете использовать отладчик для визуализации стековых фреймов при выполнении вашей рекурсии.

Позволяет проанализировать его на простом BST, например: 

      2

  1       3

Начать с корня = 2 (TopStackFrame: {root = 2, k = 3, cnt = 0, val = -1000})

|

root! = null

|

то есть 1 (TopStackFrame: {root = 1, k = 3, cnt = 0, val = -1000})

|

теперь идет слева от 1 (TopStackFrame: {root= null, k = 3, cnt = 0, val = -1000})

|

корень равен нулю, он возвращает val (верхняя часть стека удалена)

|

теперь возвращаются к 1

|

cnt ++ cnt становится 1 (TopStackFrame: {root = 1, k = 3, cnt = 1, val = -1000})

|

cnt! = K идет справа от 1 (TopStackFrame: {root = null, k = 3 cnt = 1, val = -1000})

|

справа от 1 - ноль, возвращает значение val (верхняя часть стека удалена)

|

, а затем снова возвращает значение val (TopStackFrame: {root =1, k = 3, cnt = 1, val = -1000})

|

, теперь 1 готово.

|

теперь вы пришли к 2 (TopStackFrame: {root = 2, k = 3, cnt = 0, val = -1000})

сейчас Вы видите, что значение cnt не 1, а 0, потому что у каждого стекового кадра есть свой собственный набор переменных.

Подобное происходит с переменной val.

Существует нескольковарианты решения этой проблемы:

a) Вы можете объявить их как переменные-члены в своем классе и обновить их в своей рекурсии, чтобы вам не нужно было возвращать что-либо с помощью вашей рекурсии, просто объявите метод, который ничего не возвращаетно обновляет эти переменные-члены.

b) Вы можете использовать массивы типа int [] val, int [] cnt, каждый из которых содержит один элемент, и обновлять их элементы в каждом рекурсивном вызове.

c) Вы можете использовать итеративный обход по порядку и получить значение, когда число достигает k.

Я бы предпочел 'c'.Это намного чище, не нужно объявлять переменные или массивы членов.Это также предотвращает исключения переполнения стека в сильно несбалансированных деревьях.

...