在JavaScript中实现一个计算树节点级别的方法。

huangapple go评论115阅读模式
英文:

Implement a method in Javascript that calculates the level of a tree node

问题

给定一个如下所示的树 - 请注意,这不是二叉树:

  1. 根节点
  2. / \
  3. A B
  4. / \ / \
  5. C D E F
  6. / \ \
  7. G H I

我想要编写一个方法,该方法返回我调用它时节点的层级。例如,当调用 C.getLevel() 时,我期望返回值为 2,假设根节点的层级为 0。

每个节点只有两个属性:名称和其直接子节点的数组。

由于我在处理一棵树,我有一种感觉我需要递归解决这个问题。因此,在第一步中,我需要找出一个退出条件 - 何时会返回我的方法?很可能是当没有子节点时。

我不太确定如何解决这个问题,但为了让我们有点东西可以一起工作,我将发布一个起始方法:

  1. getLevel(level = 0) {
  2. if (this.children.length === 0) {
  3. return level;
  4. }
  5. for (let child of this.children) {
  6. level = child.getLevel(level + 1);
  7. }
  8. }

有人可以帮助我解决这个问题吗?

英文:

Given a tree such as the following - please note this is NOT a binary tree:

  1. root
  2. / \
  3. A B
  4. / \ / \
  5. C D E F
  6. / \ \
  7. G H I

I would like to write a method, which returns the level of the node I call the method on. For example, when calling C.getLevel() I am expecting the return value 2, assuming the level of the root node is 0.

Each node has but two properties: a name and an array of its direct children.

Since I am working with a tree here, I have a feeling I need to solve this issue recursively. So, in a first step, I have to figure out an exit condition - when is my method going to return? Most likely when there are no children.

I don't really have a good approach for this issue, but just to give us something to work with, I'll post a start method:

  1. getLevel(level = 0) {
  2. if (this.children.length === 0) {
  3. return level;
  4. }
  5. for (let child of this.children) {
  6. level = child.getLevel(level + 1);
  7. }
  8. }

Can somebody help me figure this out?

答案1

得分: 1

你需要从根节点开始搜索,然后查找节点。这可以基于作为参数给定的节点实例,也可以基于目标节点的名称(在示例中是 "C")进行搜索。

请注意,我更喜欢将这个方面称为 深度 而不是 级别,但它是相同的概念

以下是一个通过名称搜索节点的实现,从根节点开始(我将方法命名为 getDepth):

  1. class Node {
  2. constructor(name, ...children) {
  3. this.name = name;
  4. this.children = children;
  5. }
  6. getDepth(name) {
  7. if (this.name == name) return 0;
  8. for (const child of this children) {
  9. const level = child.getDepth(name);
  10. if (level >= 0) return level + 1;
  11. }
  12. return -1; // 找不到节点
  13. }
  14. }
  15. // 构建示例树
  16. const root = new Node("root",
  17. new Node("A",
  18. new Node("C",
  19. new Node("G"),
  20. new Node("H"),
  21. new Node("I")
  22. ),
  23. new Node("D")
  24. ),
  25. new Node("B",
  26. new Node("E"),
  27. new Node("F")
  28. )
  29. );
  30. const level = root.getDepth("C");
  31. console.log(level); // 2

你提到了注释中的相反方法签名,这也是一种可能性。就像这样:

  1. class Node {
  2. constructor(name, ...children) {
  3. this.name = name;
  4. this.children = children;
  5. }
  6. getDepthWithRespectTo(root) {
  7. if (this === root) return 0;
  8. for (const parent of root.children) {
  9. const level = this.getDepthWithRespectTo(parent);
  10. if (level >= 0) return level + 1;
  11. }
  12. return -1; // 找不到节点
  13. }
  14. }
  15. // 构建示例树,并保留对节点 "C" 的引用
  16. let node;
  17. const root = new Node("root",
  18. new Node("A",
  19. node = new Node("C",
  20. new Node("G"),
  21. new Node("H"),
  22. new Node("I")
  23. ),
  24. new Node("D")
  25. ),
  26. new Node("B",
  27. new Node("E"),
  28. new Node("F")
  29. )
  30. );
  31. const level = node.getDepthWithRespectTo(root);
  32. console.log(level); // 2
英文:

You need to start the search from the root and then look to find the node. This could either be based on a node instance that is given as argument, or on a name that the target node has ("C" in the example).

Note that I prefer to call this aspect depth instead of level -- but it's the same thing.

Here is an implementation that searches for the node by name, starting at the root (I named the method getDepth):

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

  1. class Node {
  2. constructor(name, ...children) {
  3. this.name = name;
  4. this.children = children;
  5. }
  6. getDepth(name) {
  7. if (this.name == name) return 0;
  8. for (const child of this.children) {
  9. const level = child.getDepth(name);
  10. if (level &gt;= 0) return level + 1;
  11. }
  12. return -1; // Not found here
  13. }
  14. }
  15. // Build the example tree
  16. const root = new Node(&quot;root&quot;,
  17. new Node(&quot;A&quot;,
  18. new Node(&quot;C&quot;,
  19. new Node(&quot;G&quot;),
  20. new Node(&quot;H&quot;),
  21. new Node(&quot;I&quot;)
  22. ),
  23. new Node(&quot;D&quot;)
  24. ),
  25. new Node(&quot;B&quot;,
  26. new Node(&quot;E&quot;),
  27. new Node(&quot;F&quot;)
  28. )
  29. );
  30. const level = root.getDepth(&quot;C&quot;);
  31. console.log(level); // 2

<!-- end snippet -->

You mentioned an opposite method signature in comments, which is also a possibility. Like this:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

  1. class Node {
  2. constructor(name, ...children) {
  3. this.name = name;
  4. this.children = children;
  5. }
  6. getDepthWithRespectTo(root) {
  7. if (this === root) return 0;
  8. for (const parent of root.children) {
  9. const level = this.getDepthWithRespectTo(parent);
  10. if (level &gt;= 0) return level + 1;
  11. }
  12. return -1; // Not found here
  13. }
  14. }
  15. // Build the example tree, and keep a reference to node &quot;C&quot;
  16. let node;
  17. const root = new Node(&quot;root&quot;,
  18. new Node(&quot;A&quot;,
  19. node = new Node(&quot;C&quot;,
  20. new Node(&quot;G&quot;),
  21. new Node(&quot;H&quot;),
  22. new Node(&quot;I&quot;)
  23. ),
  24. new Node(&quot;D&quot;)
  25. ),
  26. new Node(&quot;B&quot;,
  27. new Node(&quot;E&quot;),
  28. new Node(&quot;F&quot;)
  29. )
  30. );
  31. const level = node.getDepthWithRespectTo(root);
  32. console.log(level); // 2

<!-- end snippet -->

答案2

得分: 0

因为你无论如何都要迭代整个树,所以一次性预先计算所有节点的深度可能会更容易:

  1. function setDepth(node, depth) {
  2. node.depth = depth
  3. for (let c of node.children)
  4. setDepth(c, depth + 1)
  5. }
  6. setDepth(root, 0)

然后只需选择 someNode.depth

英文:

Since you're going to iterate the whole tree anyway, it might be easier to precompute depths for all nodes at once:

  1. function setDepth(node, depth) {
  2. node.depth = depth
  3. for (let c of node.children)
  4. setDepth(c, depth + 1)
  5. }
  6. setDepth(root, 0)

and then just pick someNode.depth

答案3

得分: 0

class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}

addChild(child) {
this.children.push(child);
}
}

function calculateNodeLevel(root, targetValue) {
if (root.value === targetValue) {
return 0; // Found the target node at the root level
}

for (let child of root.children) {
const level = calculateNodeLevel(child, targetValue);
if (level !== -1) {
return level + 1; // Found the target node in a child subtree
}
}

return -1; // Target node not found in the tree
}

// Example usage:
const tree = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
const grandchild = new TreeNode(4);
child2.addChild(grandchild);
tree.addChild(child1);
tree.addChild(child2);

console.log(calculateNodeLevel(tree, 1)); // Output: 0
console.log(calculateNodeLevel(tree, 2)); // Output: 1
console.log(calculateNodeLevel(tree, 3)); // Output: 1
console.log(calculateNodeLevel(tree, 4)); // Output: 2
console.log(calculateNodeLevel(tree, 5)); // Output: -1 (Node not found)

英文:
  1. class TreeNode {
  2. constructor(value) {
  3. this.value = value;
  4. this.children = [];
  5. }
  6. addChild(child) {
  7. this.children.push(child);
  8. }
  9. }
  10. function calculateNodeLevel(root, targetValue) {
  11. if (root.value === targetValue) {
  12. return 0; // Found the target node at the root level
  13. }
  14. for (let child of root.children) {
  15. const level = calculateNodeLevel(child, targetValue);
  16. if (level !== -1) {
  17. return level + 1; // Found the target node in a child subtree
  18. }
  19. }
  20. return -1; // Target node not found in the tree
  21. }
  22. // Example usage:
  23. const tree = new TreeNode(1);
  24. const child1 = new TreeNode(2);
  25. const child2 = new TreeNode(3);
  26. const grandchild = new TreeNode(4);
  27. child2.addChild(grandchild);
  28. tree.addChild(child1);
  29. tree.addChild(child2);
  30. console.log(calculateNodeLevel(tree, 1)); // Output: 0
  31. console.log(calculateNodeLevel(tree, 2)); // Output: 1
  32. console.log(calculateNodeLevel(tree, 3)); // Output: 1
  33. console.log(calculateNodeLevel(tree, 4)); // Output: 2
  34. console.log(calculateNodeLevel(tree, 5)); // Output: -1 (Node not found)
  35. In this example, the TreeNode class represents a node in the tree, and it has a value property to store the value of the node and a children array to store its child nodes.
  36. The calculateNodeLevel function takes a root node and a targetValue as input. It recursively traverses the tree starting from the root and checks if the value of each node matches the targetValue. If a match is found, it returns the level of that node (0 for the root level, 1 for its children, and so on). If the targetValue is not found in the tree, it returns -1.
  37. In the example usage section, a simple tree is created, and the calculateNodeLevel function is called with different target values to demonstrate its usage and output.

huangapple
  • 本文由 发表于 2023年5月21日 22:12:10
  • 转载请务必保留本文链接:https://go.coder-hub.com/76300318.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定