Как найти числа, меньшие, чем N в несортированном дереве

Question

Как найти числа, меньшие, чем N в несортированном дереве. Мне задали этот вопрос на собеседовании. Мой ответ состоял в том, что я должен проверить все узлы, начиная с корня, или я сначала закажу дерево. Любые другие идеи?

Answer 1

Если это несортированное дерево, вы должны проверить каждый узел по определению. Если вы должны проверить все, кроме одного узла, невозможно определить, следует ли увеличить счет на 1 или нет, не проверив последний узел.

Предполагая, что вам не разрешено изменять дерево (большинство вопросов, подобных этому, вам не нравится, когда вы изменяете структуру), вы точно смотрите на решение O(n). Однако тогда возникает вопрос, каким будет наилучший способ реализации решения. Потому что это дерево, ответ (и то, что искал интервьюер) почти наверняка рекурсия.

Если у нас есть класс, который выглядит примерно так (я предполагаю, что в общем случае дерева Если это бинарное дерево просто заменить детей с левым и правым.):

public class TreeNode{ 
    private int val; 
    private Set<TreeNode> children; 
} 

Тогда мы можем добавить меньше, чем N метод класса как такового:

public class TreeNode{ 
    private int val; 
    private Set<TreeNode> children; 

    public int lessThanNCount(int n){ 
     int count = (val < n ? 1 : 0); 
     if(children != null){ 
      for(TreeNode tn : children){ 
       count += tn.lessThanNCount(n); 
      } 
     } 
     return count; 
    } 
} 

Если ваша цель состоит в том, чтобы собрать цифры, а не получить количество из них, то попробуйте следующее:

public class TreeNode{ 
    private int val; 
    private Set<TreeNode> children; 

    public ArrayList<Integer> lessThanNVals(int n){ 
     ArrayList<Integer> vals = new ArrayList<Integer>(); 
     if(val < n) vals.add(val); 
     if(children != null){ 
      for(TreeNode tn : children){ 
       vals.addAll(tn.lessThanNCount(n)); 
      } 
     } 
     return vals; 
    } 
}