Блог

Я занимался проблемой алгоритма и столкнулся с этой проблемой, когда вы решаете сумму глубин узлов (расстояние между узлом в BST и корнем дерева).

Я был смущен тем, откуда они деструктурируют узел и глубину stack.pop() .

Какова цель этого? И почему это повторяется 1 по глубине за цикл?

 function nodeDepths(root) {  console.log("root", root);  let depthSum = 0;  const stack = [{ node: root, depth: 0 }];  while (stack.length gt; 0) {  const { node, depth } = stack.pop();  console.log("node,", node, "depth", depth);  if (node === null) continue;  depthSum  = depth;  stack.push({ node: node.left, depth: depth   1 });  stack.push({ node: node.right, depth: depth   1 });  }  return depthSum; }  

Я был сбит с толку, где они деструктурируют узел и глубину из stack.pop(); Какова цель этого?

Циклу while нужны как node свойства, так и depth свойства, и они были объединены в объект, который был помещен в стек.

 const { node, depth } = stack.pop();  if (node === null) continue; // node--^ v---------depth  depthSum  = depth;  stack.push({ node: node.left, depth: depth   1 }); // /  // node----------------   ----- depth //  /  stack.push({ node: node.right, depth: depth   1 });  

И почему это повторяется 1 по глубине за цикл?

Дети находятся на один уровень глубже, чем их родители, поэтому мы добавляем еще один.

Безусловно, возможна более простая рекурсивная версия этой функции, в которой вам не нужно поддерживать стек:

 const depthSum = (node, depth = 0) =gt;   node == null  ? 0  : depth   depthSum (node .left, depth   1)   depthSum (node .right, depth   1)  const tree = { // Depth  value: 'a', // 0  left: {  value: 'b', // 1  left: {  value: 'c' // 2  },  right: {  value: 'd', // 2  left: {  value: 'e', // 3  right: {  value: 'f' // 4  }  }  }  },  right: {  value: 'g', // 1  left: {  value: 'h' // 2  },  right: {  value: 'i' // 2  } //  ___  } // 17 }  console .log (depthSum (tree)) 

Этот код более простой и прямой. Но это менее эффективно и, в зависимости от глубины вашего дерева, может привести к ограничениям глубины рекурсии. На оригинал это не распространяется. Вам нужно будет позвонить для собственных нужд.