Задача

Задача

JavaScript test

Условие: дано бинарное дерево, необходимо посчитать количество качественных узлов (Х) по пути из корня до узла Х.


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


Пример:


Ввод: root = [3,1,4,3,null,1,5]

Вывод: 4

Объяснение: *качественные узлы помечены голубым цветом на вложении.


Решение:


// Time complexity: O(n)

// Space complexity: O(n)


var goodNodes = function(root) {

  let count = 0;

  

  function dfs(root, max) {

    if (root == null)

      return;

     

    if (root.val >= max) {

      max = root.val;

      count++;

    }

     

    dfs(root.left, max);

    dfs(root.right, max);

  }

 

 dfs(root, root.val);

  return count;

};

Report Page