JavaScript - 如何在节点搜索中返回树的分支？

Question

我的数据结构是这样的：

var tree = [ 
    { 
     id: 1, 
     children: [] 
    }, { 
     id: 2, 
     children: [ 
      { 
       id: 3, 
       children: [] 
      } 
     ] 
    } 
]; 

可以有一个分支任意数量的节点或儿童。

我的目标是从顶部（根）节点开始，搜索给定节点并返回它所在的分支。

所以在Plunker的例子：https://plnkr.co/edit/PyR3H7mM0vrFyno1l7R5?p=catalogue

我要寻找节点ID＃31，所以该算法将返回数组（分支）是31的一部分。

我已经开始算法，但如果我递归地做，我不知道如何再次退出。

function traverse(branch) { 

    for (var i = 0; i < branch.length; i++) { 
    if (branch[i].id == node.id) { 
     return branch; 
    } 
    } 

    for (var j = 0; j < branch.length; j++) { 
    if (branch[j].children.length > 0) { 
     return traverse(branch[j].children); 
    } 
    } 

} 

console.log(traverse(tree)); 

例如，如果我往下看的最后一个子节点没有找到一个匹配，那么我需要回溯到父分支尝试下一组选项。

如何修改我的算法以重新找回？

Answer 1

你的算法是非常密切的，你只需要添加一个if语句，以便它只返回从traverse递归的结果，如果找到匹配：

function traverse(branch) { 

    for (var i = 0; i < branch.length; i++) { 
    if (branch[i].id == node.id) { 
     return branch; 
    } 
    } 

    for (var j = 0; j < branch.length; j++) { 
    var result = traverse(branch[j].children); 
    if (result !== undefined) { 
     return result; 
    } 
    } 

    return undefined; // no match found 

} 

console.log(traverse(tree)); 

Answer 2

你可以使用一个临时变量的结果如果数值是真的，则退出循环。

function traverse(branch) { 
    var result; 
    for (var i = 0; i < branch.length; i++) { 
     if (branch[i].id === node.id) { 
      return branch; 
     } 
     if (branch[j].children.length > 0) { 
      result = traverse(branch[j].children); 
      if (result) { 
       return result; 
      } 
     } 
    } 
} 

Answer 3

这并获得成功返回分支，而不是节点本身：

function traverse(branch) { 

     for (var i = 0; i < branch.length; i++) { 
      if (branch[i].id == node.id) { 
       return branch[i].children; 
      } 
     } 

     for (var j = 0; j < branch.length; j++) { 
      var result = traverse(branch[j].children); 
      if (result !== null) { 
       return result; 
      } 
     } 

     return null; // no match found 
    }