javascript - 从给定节点查找树中父节点的路径

Question

给定下面描述的树，给定节点说9 打印从给定节点到根的路径节点。

let sampleData = {
id: 1,
children: [{
    id: 2,
    children: [{
        id: 5,
        children: [{
            id: 8
        }]
    },
        {
            id: 6
        }
    ]
},
    {
        id: 3,
        children: [{
            id: 9
        }, {id: 10 }]}, {
        id: 4
     }
     ]
  }

例如，如果给定 9，则输出应为 1 , 3, 9

Answer 1

按照建议，您可以使用 dfs 算法。

function dfs(o, target){
    if(o.id == target) return [target];
    if(!o.children) return false;
    let path;
    o.children.find(x=>path=dfs(x, target));
    if(path){
        return [o.id].concat(path);
    }
};
let sampleData={"id":1,"children":[{"id":2,"children":[{"id":5,"children":[{"id":8}]},{"id":6}]},{"id":3,"children":[{"id":9},{"id":10}]},{"id":4}]}
let path;
[sampleData].find(x=>path=dfs(x, 9))
console.log(path);