Рубрики

Самый глубокий левый листовой узел в двоичном дереве

По заданному двоичному дереву найдите самый глубокий листовой узел, который остается дочерним от его родителя. Например, рассмотрим следующее дерево. Самый глубокий левый листовой узел — это узел со значением 9.

       1
     /   \
    2     3
  /      /  \  
 4      5    6
        \     \
         7     8
        /       \
       9         10

Идея состоит в том, чтобы рекурсивно пройти заданное двоичное дерево и, обходя его, поддерживать «уровень», который будет хранить текущий уровень узла в дереве. Если текущий узел является левым листом, то проверьте, больше ли его уровень, чем уровень самого глубокого левого листа, который вы видели до сих пор. Если уровень больше, обновите результат. Если текущий узел не является листом, то рекурсивно найдите максимальную глубину в левом и правом поддеревьях и верните максимум из двух глубин. Спасибо Coder011 за предложенный подход.

C / C ++

// Программа на C ++ для поиска самого глубокого левого листа в данном двоичном дереве
#include <stdio.h>
#include <iostream>

using namespace std;

  

struct Node

{

    int val;

    struct Node *left, *right;

};

  

Node *newNode(int data)

{

    Node *temp = new Node;

    temp->val = data;

    temp->left = temp->right =  NULL;

    return temp;

}

  
// Утилита для поиска самого глубокого конечного узла
// lvl: уровень текущего узла.
// maxlvl: указатель на самый глубокий левый листовой узел, найденный до сих пор
// isLeft: bool указывает, что этот узел остался дочерним от своего родителя
// resPtr: указатель на результат

void deepestLeftLeafUtil(Node *root, int lvl, int *maxlvl,

                         bool isLeft, Node **resPtr)

{

    // Базовый вариант

    if (root == NULL)

        return;

  

    // Обновление результата, если этот узел покинул лист и его уровень больше

    // чем максимальный уровень текущего результата

    if (isLeft && !root->left && !root->right && lvl > *maxlvl)

    {

        *resPtr = root;

        *maxlvl = lvl;

        return;

    }

  

    // Повтор для левого и правого поддеревьев

    deepestLeftLeafUtil(root->left, lvl+1, maxlvl, true, resPtr);

    deepestLeftLeafUtil(root->right, lvl+1, maxlvl, false, resPtr);

}

  
// Оболочка для deepestLeftLeafUtil ().
Node* deepestLeftLeaf(Node *root)
{

    int maxlevel = 0;

    Node *result = NULL;

    deepestLeftLeafUtil(root, 0, &maxlevel, false, &result);

    return result;

}

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

int main()

{

    Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->right->left = newNode(5);

    root->right->right = newNode(6);

    root->right->left->right = newNode(7);

    root->right->right->right = newNode(8);

    root->right->left->right->left = newNode(9);

    root->right->right->right->right = newNode(10);

  

    Node *result = deepestLeftLeaf(root);

    if (result)

        cout << "The deepest left child is " << result->val;

    else

        cout << "There is no left leaf in the given tree";

  

    return 0;

}

Джава

// Java-программа для поиска
// самый глубокий левый лист
// в двоичном дереве

  
// Узел двоичного дерева

class Node

{

    int data;

    Node left, right;

  

    // Конструктор

    public Node(int data)

    {

        this.data = data;

        left = right = null;

    }

}

  
// Класс для оценки прохода
// по ссылке

class Level 

{

    // maxlevel: дает

    // значение уровня

    // максимальный левый лист

    int maxlevel = 0;

}

  

class BinaryTree 

{

    Node root;

      

    // Узел для хранения результирующего

    // узел после левого обхода

    Node result;

  

    // Функция полезности для

    // найти самый глубокий листовой узел.

    // lvl: уровень текущего узла.

    // isLeft: Bool указывает

    // этот узел остается дочерним

    void deepestLeftLeafUtil(Node node, 

                             int lvl, 

                             Level level,

                             boolean isLeft) 

    {

        // Базовый вариант

        if (node == null

            return;

  

        // Обновить результат, если этот узел

        // левый лист и его уровень

        // больше уровня maxl

        // текущего результата

        if (isLeft != false &&

            node.left == null &&

            node.right == null &&

            lvl > level.maxlevel)

        {

            result = node;

            level.maxlevel = lvl;

        }

  

        // Повтор для левого и правого поддеревьев

        deepestLeftLeafUtil(node.left, lvl + 1,

                            level, true);

        deepestLeftLeafUtil(node.right, lvl + 1,

                            level, false);

    }

  

    // Оболочка для deepestLeftLeafUtil ().

    void deepestLeftLeaf(Node node) 

    {

        Level level = new Level();

        deepestLeftLeafUtil(node, 0, level, false);

    }

      

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

    public static void main(String[] args) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.right.left = new Node(5);

        tree.root.right.right = new Node(6);

        tree.root.right.left.right = new Node(7);

        tree.root.right.right.right = new Node(8);

        tree.root.right.left.right.left = new Node(9);

        tree.root.right.right.right.right = new Node(10);

  

        tree.deepestLeftLeaf(tree.root);

        if (tree.result != null)

            System.out.println("The deepest left child"+

                               " is " + tree.result.data);

        else

            System.out.println("There is no left leaf in"+

                               " the given tree");

    }

}

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

питон

# Программа Python, чтобы найти самый глубокий левый лист в данном
# Двоичное дерево

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, val):

        self.val = val 

        self.left = None

        self.right = None

  
# Полезная функция для поиска самого глубокого конечного узла.
# lvl: уровень текущего узла.
# maxlvl: указатель на самый глубокий левый листовой узел, найденный до сих пор
# isLeft: bool указывает, что этот узел оставлен дочерним
# его родителя
# resPtr: указатель на результат

def deepestLeftLeafUtil(root, lvl, maxlvl, isLeft):

      

    # Базовый вариант

    if root is None:

        return

  

    # Обновить результат, если этот узел покинул лист и его

    # уровень больше максимального уровня текущего результата

    if(isLeft is True):

        if (root.left == None and root.right == None):

            if lvl > maxlvl[0] : 

                deepestLeftLeafUtil.resPtr = root 

                maxlvl[0] = lvl 

                return

  

    # Повтор для левого и правого поддеревьев

    deepestLeftLeafUtil(root.left, lvl+1, maxlvl, True)

    deepestLeftLeafUtil(root.right, lvl+1, maxlvl, False)

  
# Обертка для левого и правого поддерева

def deepestLeftLeaf(root):

    maxlvl = [0]

    deepestLeftLeafUtil.resPtr = None

    deepestLeftLeafUtil(root, 0, maxlvl, False)

    return deepestLeftLeafUtil.resPtr

  

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

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.right.left = Node(5)

root.right.right = Node(6)

root.right.left.right = Node(7)

root.right.right.right = Node(8)

root.right.left.right.left = Node(9)

root.right.right.right.right= Node(10)

  

result = deepestLeftLeaf(root) 

  

if result is None:

    print "There is not left leaf in the given tree"

else:

    print "The deepst left child is", result.val

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

  
// AC # программа для поиска
// самый глубокий левый лист
// в двоичном дереве

  
// Узел двоичного дерева

public class Node

{

    public int data;

    public Node left, right;

  

    // Конструктор

    public Node(int data)

    {

        this.data = data;

        left = right = null;

    }

}

  
// Класс для оценки прохода
// по ссылке

public class Level

{

    // maxlevel: дает

    // значение уровня

    // максимальный левый лист

    public int maxlevel = 0;

}

  

public class BinaryTree

{

    public Node root;

  

    // Узел для хранения результирующего

    // узел после левого обхода

    public Node result;

  

    // Функция полезности для

    // найти самый глубокий листовой узел.

    // lvl: уровень текущего узла.

    // isLeft: Bool указывает

    // этот узел остается дочерним

    public virtual void deepestLeftLeafUtil(Node node, int lvl, 

                                        Level level, bool isLeft)

    {

        // Базовый вариант

        if (node == null)

        {

            return;

        }

  

        // Обновить результат, если этот узел

        // левый лист и его уровень

        // больше уровня maxl

        // текущего результата

        if (isLeft != false && node.left == null && node.right == null

                            && lvl > level.maxlevel)

        {

            result = node;

            level.maxlevel = lvl;

        }

  

        // Повтор для левого и правого поддеревьев

        deepestLeftLeafUtil(node.left, lvl + 1, level, true);

        deepestLeftLeafUtil(node.right, lvl + 1, level, false);

    }

  

    // Оболочка для deepestLeftLeafUtil ().

    public virtual void deepestLeftLeaf(Node node)

    {

        Level level = new Level();

        deepestLeftLeafUtil(node, 0, level, false);

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

        tree.root.left.left = new Node(4);

        tree.root.right.left = new Node(5);

        tree.root.right.right = new Node(6);

        tree.root.right.left.right = new Node(7);

        tree.root.right.right.right = new Node(8);

        tree.root.right.left.right.left = new Node(9);

        tree.root.right.right.right.right = new Node(10);

  

        tree.deepestLeftLeaf(tree.root);

        if (tree.result != null)

        {

            Console.WriteLine("The deepest left child is " + tree.result.data);

        }

        else

        {

            Console.WriteLine("There is no left leaf in the given tree");

        }

    }

}

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

Выход:

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

Самый глубокий левый листовой узел в двоичном дереве

0.00 (0%) 0 votes