Как определить листовые узлы бинарного дерева поиска

Question

Недавно я наткнулся на следующую проблеме, что было сказано, что было предложено в техническом интервью:

Учитывая обход бинарного дерева поиска, как мы идентифицируем листовые узлы без построения дерева?

Например: [5,3,2,4,8,7,9]

вопрос был оставлен расплывчатым тот, кто отправил его и дал неясности, я не совсем уверен, что такой подход должен быть для этого, и я не смог найти проверенные решения в Интернете.

Как решить эту проблему?

Answer 1

Рассмотрим ваш пример: [5,3,2,4,8,7,9]

Возьмите первый элемент: 5.

Поскольку это обходе это корневой узел наверняка.

Теперь в обходе, после того, как корень у повторялись для левого поддерева, а затем правое поддерево.

И у также известно, что в BST:

nodes in left subtree < root < nodes in right subtree 

Следовательно, после того, как 5, все элементы серии , которые менее чем 5 принадлежит левое поддерево. И аналогично для права.

Так у в конечном итоге, это (вам не нужно явно создать дерево):

 5 
    / \ 
    [3,2,4] [8,7,9] 

Теперь [3,2,4] является обходом для левой части поддерева и [8,7,9] для правых.

Рекурсия для обоих суб-массивов и момент u оставляются с массивом размера 1, это лист.

Answer 2

Я предполагаю, что рассмотрим только perfect BST. Потому что, если это не идеально, могут быть (возможно) несколько ответов.

Так что, глядя на примеры и описание preorder traversal, очевидно, что сначала берутся корни, а затем «вниз» к листьям. Поскольку у нас есть идеальное дерево, мы можем видеть, что листья всегда идут парами. А также нам нужно «пропустить» своих родителей.

Наглядно Я предложил бы идти в обратном направлении, а 2 последние элементы листья ('*' означает не листья):

< [*,*,2,4,*,7,9] - The Overal процедура выглядит следующим образом (движение назад):

1. взять 2 листа;
2. пропустить 1 узел (их родительский элемент);
3. повторные шаги [1-2];
4. пропустить еще 1 узел (родитель родителей);
5. сделано (осталось больше элементов).

Теперь демо на большом массиве (15 элементов, снова идеальное дерево)

[*,*,*,l,l,*,l,l,*,*,l,l,*,l,l] < - где l обозначает лист. Этапы (также назад):

1. 1-4 из примера prevoius;
2. еще раз 1-4 из предыдущего примера;
3. пропустить еще 1 узел (родитель родителей родителей);
4. сделано (не более элементов).

Надеюсь, у вас есть идея.

Что касается коммунистической программы подхода, вы можете обнаружить повторяющийся рисунок в выше интуитивном подходе и использовать рекурсию в зависимости от высоты дерева (можете быть easilly вычисляются как log2(n+1) где n является количеством элементов в дереве, также выглядит wiki) но, вероятно, начиная с начала массива.Псевдокод:

void getLeaves(int height) { 
    if (height == 2) {  // there is only a parent and two childs (leaves) 
     skip(1);    // skip 1 element 
     take(2);    // next two are leaves, get them 
    } 
    else { 
     skip(1);    // skip parent of parents (of parents ...) 
     getLeaves(height-1); // call on left part of array 
     getLeaves(height-1); // call on right part of array 
    } 
} 

Answer 3

void printleafnode(int*arr, int size) 
{ 
    int i = 0; 

    while(i < size) 
    { 
     if(arr[i] > arr[i+1]) 
      i= i+1; 
     else 
     { 
      if(arr[i] < arr[i+1]) 
      { 
       printf(" %d " ,arr[i]); 
       i= i+1; 
      } 
     } 
    } 
    printf(" %d ", arr[i]); 
    printf("\n"); 
} 

Answer 4

import java.util.ArrayList; 

public class PreorderArrayToTree { 

    static void printLeafNodes(ArrayList<Integer> list) { 
     if(list.size()==0)return; 
     if(list.size()==1) { 
      System.out.print(list.get(0)+" "); 
      return; 
     } 
     int parent = list.get(0); 
     ArrayList<Integer> leftChild = new ArrayList<Integer>(); 
     ArrayList<Integer> rightChild = new ArrayList<Integer>(); 
     for(int i=1; i<list.size(); i++) { 
      if(list.get(i)<parent)leftChild.add(list.get(i)); 
      if(list.get(i)>parent)rightChild.add(list.get(i)); 
     }; 
     printLeafNodes(leftChild); 
     printLeafNodes(rightChild); 
    }; 

    public static void main(String[] args) { 
     //int[] arr = {10,5,1,7,40,50}; 
     //int[] arr = {890, 325, 290, 530, 965}; 
     int[] arr = {3,2,4}; 
     ArrayList<Integer> list = new ArrayList<Integer>(); 
     for(int i=0; i<arr.length; i++)list.add(arr[i]); 
     printLeafNodes(list); 
    }; 
};