Как обработать объект в рекурсии JS

295

15 ноября 2017, 02:45

Как правильно обработать объект в рекурсии, чтобы можно было искать min, max среди value?

структура объекта:

Node = {
    value: <number>,
    children: [Node]
}

функция:

const deepMap = (obj) =>{
        //maxValue =(maxValue.value < obj.value) ? obj : maxValue;
        console.log( obj);
        obj.children ? obj.children.map(item => deepMap(item)) : obj;
};

часть объекта

var graph = {
    value: 75,
    children: [{
        value: 18,
        children: [{
            value: 35,
            children: [{
                value: 35,
                children: [{
                    value: 66,
                    children: [{
                        value: 29,
                        children: [{value: 85}]
                    }]
                }]
            }]
        }]
    }]
}

Answer 1

В примере кода в вопросе отсутствует return, следовательно данная функция ничего не выводит, но она уже пробегает по всем элементам в графе.

Первое что нужно изменить: добавить return, который будет возвращать нужное значение.

Нужным в данном случае является максимум из нескольких чисел: значения поля value, и значений из поля children.

Применяя функцию deepMap к каждому элементу массива children можно на каждом уровне иметь список максимальных значений.

Для нахождения максимального числа из нескольких можно применить функцию Math.max, а так же spread operator, позволяющей удобно передать в нее массив.

Так как поле children может отсутствовать, нужно добавить соответствующую проверку и в случае ее выполнения сразу возвращать value.

Приняв все замечания, функцию можно изменить так:

const deepMap = (obj) => {
  if (!obj.children) return obj.value; // если нет детей - сразу вернуть value
  var maxChildren = obj.children.map(deepMap); // получаем максимальных из детей
  return Math.max(obj.value, ...maxChildren); // возвращаем максимальное из значений.
};

Если убрать локальные переменные и if можно получить следующий вариант:

function deepMax(obj){
    return Math.max(obj.value, ...(obj.children||[]).map(deepMax));
}

Пример:

const deepMap = (obj) => { 
  if (!obj.children) return obj.value; // если нет детей - сразу вернуть value 
  var maxChildren = obj.children.map(deepMap); // получаем максимальных из детей 
  return Math.max(obj.value, ...maxChildren); // возвращаем максимальное из значений. 
}; 
 
var graph = { 
  value: 75, 
  children: [{ 
    value: 18, 
    children: [{ 
      value: 35, 
      children: [{ 
        value: 35, 
        children: [{ 
          value: 66, 
          children: [{ 
            value: 29, 
            children: [{ 
              value: 85 
            }] 
          }] 
        }] 
      }] 
    }] 
  }] 
} 
 
console.log(deepMap(graph));

Answer 2

Для данной структуры я бы предложил такое решение:

const graph = { 
    value: 75, 
    children: [{ 
        value: 18, 
        children: [{ 
            value: 35, 
            children: [{ 
                value: 35, 
                children: [{ 
                    value: 66, 
                    children: [{ 
                        value: 29, 
                        children: [{value: 85}] 
                    }] 
                }] 
            }] 
        }] 
    }] 
} 
 
// Функция deepMap рекурсивно обходит дерево obj 
// Второй параметр func - необходимая функция сравнения 
function deepMap(obj, func){ 
    if(obj.children){ // Если есть потомки - то уходим в рекурсию 
      let res = obj.value; 
      // Рекурсивно проходим по всем потомкам и вычисляем результат 
      for(let i = 0; i < obj.children.length; i++) { 
         res = func(res, deepMap(obj.children[i], func)); 
      }   
      return res; 
    } else { // Нет потомков - возвращаем значение  
      return obj.value 
    }   
  } 
   
  console.log(`Max result for graph is: ${deepMap(graph, Math.max)}`); 
 
  console.log(`Min result for graph is: ${deepMap(graph, Math.min)}`);