节点深度算法澄清

Question

我在做一个算法问题，遇到了这个问题，你可以求解节点深度的总和(BST中节点和树根之间的距离(。

我对他们在哪里从stack.pop()分解节点和深度感到困惑。

这样做的目的是什么？为什么每个循环的深度迭代+1？

function nodeDepths(root) {
console.log("root", root);
let depthSum = 0;
const stack = [{ node: root, depth: 0 }];
while (stack.length > 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;
}

Answer 1

我很困惑他们在哪里从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) => 
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))

此代码更简单、更直接。但它的效率较低，而且根据树的深度，可能会遇到递归深度限制。原件不受此约束。你需要为自己的用途打电话。