Рубрики

Проверьте, имеет ли каждый внутренний узел BST ровно один дочерний элемент

Учитывая прохождение предзаказа BST, проверьте, есть ли у каждого неконечного узла только один дочерний узел. Предположим, что BST содержит уникальные записи.

Примеры

Input: pre[] = {20, 10, 11, 13, 12}
Output: Yes
The give array represents following BST. In the following BST, every internal
node has exactly 1 child. Therefor, the output is true.
        20
       /
      10
       \
        11
          \
           13
           /
         12

В обходе Предзаказа потомки (или преемники Преемдера) каждого узла появляются после узла. В приведенном выше примере 20 является первым узлом в предзаказе, и все потомки 20 появляются после него. Все потомки 20 меньше его. Для 10 все потомки больше его. В общем, мы можем сказать, что если все внутренние узлы имеют только одного дочернего элемента в BST, то все потомки каждого узла либо меньше, либо больше, чем узел. Причина проста, поскольку дерево является BST, и у каждого узла есть только один дочерний элемент, все потомки узла будут либо слева, либо справа, то есть все потомки будут меньше или больше.

Подход 1 (Наивный)
Этот подход просто следует вышеупомянутой идее, что все значения на правой стороне либо меньше, либо больше. Используйте два цикла, внешний цикл выбирает элемент один за другим, начиная с самого левого элемента. Внутренний цикл проверяет, все ли элементы на правой стороне выбранного элемента меньше или больше. Временная сложность этого метода будет O (n ^ 2).

Подход 2
Поскольку все потомки узла должны быть больше или меньше, чем узел. Мы можем сделать следующее для каждого узла в цикле.
1. Найдите следующий пре-заказ преемника (или потомка) узла.
2. Найдите преемника последнего предзаказа (последний элемент в pre []) узла.
3. Если оба преемника меньше текущего узла или оба преемника больше текущего узла, продолжайте. Иначе верните ложь.

С

#include <stdio.h>

  

bool hasOnlyOneChild(int pre[], int size)

{

    int nextDiff, lastDiff;

  

    for (int i=0; i<size-1; i++)

    {

        nextDiff = pre[i] - pre[i+1];

        lastDiff = pre[i] - pre[size-1];

        if (nextDiff*lastDiff < 0)

            return false;;

    }

    return true;

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    int pre[] = {8, 3, 5, 7, 6};

    int size = sizeof(pre)/sizeof(pre[0]);

    if (hasOnlyOneChild(pre, size) == true )

        printf("Yes");

    else

        printf("No");

    return 0;

}

Джава

// Проверяем, есть ли у каждого внутреннего узла BST только один дочерний элемент

  

class BinaryTree {

  

    boolean hasOnlyOneChild(int pre[], int size) {

        int nextDiff, lastDiff;

  

        for (int i = 0; i < size - 1; i++) {

            nextDiff = pre[i] - pre[i + 1];

            lastDiff = pre[i] - pre[size - 1];

            if (nextDiff * lastDiff < 0) {

                return false;

            };

        }

        return true;

    }

  

    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();

        int pre[] = new int[]{8, 3, 5, 7, 6};

        int size = pre.length;

        if (tree.hasOnlyOneChild(pre, size) == true) {

            System.out.println("Yes");

        } else {

            System.out.println("No");

        }

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Проверьте, если каждый внутренний
# узел BST имеет только одного ребенка

  

def hasOnlyOneChild (pre, size):

    nextDiff=0; lastDiff=0

   

    for i in range(size-1):

        nextDiff = pre[i] - pre[i+1]

        lastDiff = pre[i] - pre[size-1]

        if nextDiff*lastDiff < 0:

            return False

    return True

   
# драйвер программы для
# проверка над функцией

if __name__ == "__main__":

  

    pre = [8, 3, 5, 7, 6]

    size= len(pre)

  

    if (hasOnlyOneChild(pre,size) == True):

        print("Yes")

    else:

        print("No")

  
# Этот код предоставлен
# Харшит Сайни


Выход:

 Yes 

Подход 3
1. Просканируйте последние два узла предварительного заказа и отметьте их как мин. И макс.
2. Сканирование каждого узла в массиве предварительного заказа. Каждый узел должен быть либо меньше минимального узла, либо больше максимального узла. Обновите мин и макс соответственно.

С

#include <stdio.h>

  

int hasOnlyOneChild(int pre[], int size)

{

    // Инициализируем мин и макс, используя последние два элемента

    int min, max;

    if (pre[size-1] > pre[size-2])

    {

        max = pre[size-1];

        min = pre[size-2]):

    else

    {

        max = pre[size-2];

        min = pre[size-1];

    }

  

  

    // Каждый элемент должен быть меньше чем min или

    // больше чем макс

    for (int i=size-3; i>=0; i--)

    {

        if (pre[i] < min)

            min = pre[i];

        else if (pre[i] > max)

            max = pre[i];

        else

            return false;

    }

    return true;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int pre[] = {8, 3, 5, 7, 6};

    int size = sizeof(pre)/sizeof(pre[0]);

    if (hasOnlyOneChild(pre,size))

        printf("Yes");

    else

        printf("No");

    return 0;

}

Джава

// Проверяем, есть ли у каждого внутреннего узла BST только один дочерний элемент

  

class BinaryTree {

  

    boolean hasOnlyOneChild(int pre[], int size) {

        // Инициализируем мин и макс, используя последние два элемента

        int min, max;

        if (pre[size - 1] > pre[size - 2]) {

            max = pre[size - 1];

            min = pre[size - 2];

        } else {

            max = pre[size - 2];

            min = pre[size - 1];

        }

  

        // Каждый элемент должен быть меньше чем min или

        // больше чем макс

        for (int i = size - 3; i >= 0; i--) {

            if (pre[i] < min) {

                min = pre[i];

            } else if (pre[i] > max) {

                max = pre[i];

            } else {

                return false;

            }

        }

        return true;

    }

  

    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();

        int pre[] = new int[]{8, 3, 5, 7, 6};

        int size = pre.length;

        if (tree.hasOnlyOneChild(pre, size) == true) {

            System.out.println("Yes");

        } else {

            System.out.println("No");

        }

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Проверьте, если каждый внутренний
# узел BST имеет только одного ребенка
# подход 2

  

def hasOnlyOneChild(pre,size):

  

    # Инициализировать мин и макс

    # используя последние два элемента

    min=0; max=0

  

    if pre[size-1] > pre[size-2] :

        max = pre[size-1]

        min = pre[size-2]

    else :

        max = pre[size-2]

        min = pre[size-1

   

    # Каждый элемент должен быть

    # или меньше, чем мин или

    # больше макс

    for i in range(size-3, 0, -1):

        if pre[i] < min:

            min = pre[i]

        elif pre[i] > max:

            max = pre[i]

        else:

            return False

    return True

   
# Драйвер программы для
# проверка над функцией

if __name__ == "__main__":

  

    pre = [8, 3, 5, 7, 6]

  

    size = len(pre)

    if (hasOnlyOneChild(pre, size)):

        print("Yes")

    else:

        print("No")

  
# Этот код предоставлен
# Харшит Сайни


Выход:

Yes

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

Рекомендуемые посты:

Проверьте, имеет ли каждый внутренний узел BST ровно один дочерний элемент

0.00 (0%) 0 votes