删除节点时，pruneRoots 函数在下面的树算法中返回未定义。无法使其工作。我究竟做错了什么？

Question

我正在应对 Atlassian 的 plantyourcode 挑战。我在4.1级。我是新手。我知道树，因为关于这个问题，当在递归函数中将树的节点作为参数发送时，它们由变量接收而不是引用原始树。

我经常在递归后的最终 return 值中得到 undefined。我无法解决这个问题。必须编辑原始树，在本例中为修剪。

我在这个挑战中坚持了好几天。我尝试了我阅读的方法，观看了所有关于此的视频，我正处于放弃这一水平的挑战的边缘。在此之后我只有 2 个级别，我想进入它们装备。我需要知道正确答案背后的原因以及我的代码哪里出错了。

我就是这样学习、参与挑战、解决问题的。对我来说，这种学习很重要。我认真对待这件事。希望得到解答，加深理解。

你能帮我解决一下吗？

谢谢。

问：

编写一个函数，该函数将 return 在您修剪了所有不健康的节点（其下没有健康节点）之后，您的新根系统。

那里提供的提示：

我们有一个二叉树形式的根结构，其中 0 表示不健康，1 表示健康。空值表示节点位置为空。节点 n 的子树是 n，加上作为 n 的后代的每个节点。

二叉树节点的定义：

@param {integer} 数据 - 0 或 1
@param {Node} left - 子树或 null 表示没有左分支
@param {Node} right - 没有右分支的子树或 null

   function Node(data, left, right) {
       this.data = data === undefined ? 0 : data;
      this.left = left === undefined ? null : left;
      this.right = right === undefined ? null : right;
 }

完成以下确定要修剪哪些节点的操作，以便修剪所有没有健康节点作为子节点的不健康节点，并 return 结果。将修剪后的节点设置为空。
@param {Node} root - 代表植物根系的二叉树数据
@return {节点} - 表示植物修剪后的根系的二叉树数据

我的代码：

    function pruneRoots(root) {
        
        
        const removeNode = function(node) {
            
            
          if (node === null) {
            return null;
          }
          if (node.data === 0) {
     
            if(node.left && node.right){
                  if(node.left.data === 0 && node.right.data === 0)
                  {
                          return null;
                  }       
            }
    

            if(node.right && node.right !== null){
            node.right = removeNode(node.right);
            
            }
            if(node.left && node.left !== null){
            node.left = removeNode(node.left);
    
            }
            
          } else if(node.data === 1){
    
    
  
            if(node.right && node.right !== null){
            node.right = removeNode(node.right);
      
            }
            if(node.left && node.left != null){
            node.left = removeNode(node.left);     
           }} 
            return node 
           }
    
            var a = removeNode(root);
        
            console.log(a); //or return a
          }
    
    
 //function call, the root is structured as shown in the argument passed. 

  
    
    pruneRoots({
        "data": 1,
        "left": null,
        "right": {
            "data": 0,
            "left": {
                "data": 0,
                "left": null,
                "right": null
            },
            "right": {
                "data": 0,
                "left": null,
                "right": null
            }
        }
    });

Answer 1

您代码中的注释揭示了一些误解。

例如，下面的注释没有描述下一行代码在做什么：

// node has no children 
if (node.left && node.right){

上面的if条件实际上是在测试node是否有两个children！当 node.left 是 object（即节点）时，它是一个“真”值，当它是 null 时，它是“假”值。因此，您正在测试 node.left 和 node.right 是否都不是 null（因为这是它们在这种情况下可能具有的唯一可能的“虚假”值）。

以下评论并不总是正确的：可能是该节点只有右 child，但没有左 child -- 一个 if 条件可能为真，而另一个不是。

// node has two children 
if(node.right && node.right !== null) {

您可以改进的另一件事：

console.log(a) //since its on my code editor
//otherwise return a, for the main challenge page

你应该总是return这里。出于调试目的执行 console.log 是可以的，但确保 return 它也是如此，在测试时也是如此。

逻辑

您的算法存在逻辑错误：

if (node.left && node.right){
    if(node.left.data === 0 && node.right.data === 0) {
        return null
    }       
}

这是不对的，因为 node.left.left 仍然可以有一个值 1（即健康），所以 return null 是错误的。这里的关键见解是你应该 first 对 node.left 和 node.right 进行递归调用，然后然后检查是否结果，这些节点被修剪了。如果是这样，那么您才可以决定也修剪当前的 node（和 return null）。

递归

您创建了一个嵌套函数来执行递归。但与递归使用主 pruneRoots 函数相比，它确实没有任何优势：它采用相同类型的参数并且 returns 具有相同类型。你还不如递归地使用pruneRoots。

更正

这里是更正后的版本：

function pruneRoots(root) {
    if (root === null) {
        return null;
    }
    // First perform the recursive pruning
    root.left = pruneRoots(root.left);
    root.right = pruneRoots(root.right);
    // Now we can be sure that if a child still exists, 
    // there must be a healthy node in its subtree 
    if (root.data === 0 && !root.left && !root.right) { // Not healthy and no children
        return null;
    }
    // In all other cases, don't prune the node
    return root;
}

let result = pruneRoots({
    "data": 1,
    "left": null,
    "right": {
        "data": 0,
        "left": {
            "data": 0,
            "left": null,
            "right": null
        },
        "right": {
            "data": 0,
            "left": null,
            "right": null
        }
    }
});

console.log(result);

删除节点时，pruneRoots 函数在下面的树算法中返回未定义。无法使其工作。我究竟做错了什么？

pruneRoots function returning undefined in the below tree algorithm when removing a node. Unable to make it work. What am I doing wrong?

javascript

tree

逻辑

递归

更正