Минимальная глубина бинарного дерева в JavaScript

Минимальная глубина бинарного дерева в JavaScript

Структуры данных могут быть немного сложными, особенно для тех, у кого нет традиционной степени CS. Тем не менее, любой может улучшить их со временем и практикой. Сегодня я собираюсь показать, что вам нужно решить минимальную глубину двоичного дерева.

Двоичное дерево — это древовидная структура данных, в которой каждый узел имеет не более двух потомков, которые называются левым дочерним элементом и правым дочерним элементом. ребенок. Нахождение минимальной глубины бинарного дерева — это насколько глубоко дерево, в котором мы достигаем конечного узла. Листовой узел — это узел, у которого нет дочерних элементов.

Давайте начнем, вы можете сделать это с помощью поиска в глубину или поиска в ширину. Я использую поиск в ширину, потому что хочу сначала посетить каждый узел на одном уровне. Вы можете сделать это рекурсивно с DFS, но это зависит от вас.

В BFS мы используем очередь. Очередь — это структура данных LIFO, которая поступает последним, мы хотим посетить узел и его дочерние элементы. Мы также хотим вести общий подсчет минимальной глубины. Мы начинаем с -1, потому что, когда мы выталкиваем корень, он становится равным нулю, глубина корня всегда равна нулю, мы не углублялись

function binary_tree_min_depth(root) {

 let queue = [] 
 queue.push(root)
 let minDepth = -1
}

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

while(queue.length > 0){
        minDepth++ 
        let level = queue.length

Теперь наступает встреча с кодом, нам нужно идти уровень за уровнем и получать дочерние элементы каждого поддерева.

let level = queue.length
      for(let i = 0; i < level; i++){
          let node = queue.shift()
          //pop node off the queue 
  //if there are no left and right children thats our mindepth
          if(!node.left  && !node.right ){
              return minDepth
          }
          //if there are more nodes to left and right add to queue
          if(node.right !== null){
              queue.push(node.right)
          }
          if(node.left !== null){
              queue.push(node.left)
          }
          
      }
     }

После всего проделанного возвращаем minDepth

function binary_tree_min_depth(root) {
    // WRITE YOUR BRILLIANT CODE HERE
     let queue = [] 
    queue.push(root)
    let minDepth = -1
    while(queue.length > 0){
        minDepth++ 
        let level = queue.length
      for(let i = 0; i < level; i++){
          let node = queue.shift()
          
          if(!node.left  && !node.right ){
              return minDepth
          }
          
           if(node.right !== null){
              queue.push(node.right)
          }
          if(node.left !== null){
              queue.push(node.left)
          }
          
      }
    }
    return minDepth
}

Это! Вот как вы находите минимальную глубину двоичного дерева в Javascript.