Подсчитать количество узлов на заданном уровне бинарного дерева

Question

необходимо посчитать кол-во узлов на заданном уровне бинарного дерева, пыталась набросать функцию со счетчиками при рекурсивном обходе дерева, но понимаю, что счетчики таким образом работают неправильно... не могу никак придумать, как правильно это решить. Есть код самого класса и идеи для реализации метода на C#:

class BinaryTree //класс для хранения информации узла
        {
            public long? value { get; private set; }
            public BinaryTree left { get; set; }
            public BinaryTree right { get; set; }
            
            public void CountLevel (int level)
            {
                _CountLevel(this, level, 0, 0);
            }

            public void _CountLevel (BinaryTree currentNode, int level, int currentLevel, int n) //метод подсчета, level - заданный уровень дерева; currentLevel - номер текущего уровня; n - счетчик числа узлов
            {
                if (currentNode == null)
                {
                    return;
                }
                if (currentLevel == level) n++;
                _CountLevel(currentNode.left, level, currentLevel + 1, n);
                _CountLevel(currentNode.right, level, currentLevel + 1, n);
            }
         }

Помогите, пожалуйста, с решением, идей больше нет :(

Answer 1

Допустим, у нас есть класс узла дерева

public class TreeNode
{
    public int Val{get;set;}
    public TreeNode Left {get;set;}
    public TreeNode Right {get;set;}
}

Метод, что считает кол-во узлов на уровне можно выразить так

public int CountNodesOnLevel(TreeNode root, int level)
{
    if (root == null) return 0;
    if (level == 0) return 1;
    return CountNodesOnLevel(root.Left, level-1) + CountNodesOnLevel(root.Right, level-1);
}

Проверка

var root = new TreeNode()
{
    Left = new TreeNode()
    {
        Left = new TreeNode(),
        Right = new TreeNode()
    },
    Right = new TreeNode()
    {
        Right = new TreeNode()
    }
};
Console.WriteLine(CountNodesOnLevel(root, 2));

Вывод

БЛОГ НА HUSL

Подсчитать количество узлов на заданном уровне бинарного дерева

Ответы (1 шт):