JS算法题目3

Question

let tree = [
            {
                name: 'A',
                childs:[
                    {
                        name:'1001',
                        childs:[
                            {
                                name:'1002',
                                childs:[
                                    {
                                        name:'1003',
                                        childs:[]
                                    }
                                ]
                            }
                        ]
                    }
                ]
            },
            {
                name: 'B',
                childs:[
                    {
                        name:'1004',
                        childs:[
                            {
                                name:'1005',
                                childs:[]
                            }
                        ]
                    }
                ]
            }
        ]

//要求：给定一个树形数据结构，输入任何一个 子元素，返回他的根级元素
/**
输入：A 输出 A
输入：1001 输出 A
输入：1002 输出 A
输入：1003 输出 A
输入：B 输出 B
输入：1004 输出 B
输入：1005 输出 B
...
*/

Answer 1

function findRoot(list, cb) {
    for(var item of list) {
       if(cb(item) || (item.childs && findRoot(item.childs, cb))) return item;
    }
    return null;
}

findRoot(tree,item => item.name == 'A')
findRoot(tree,item => item.name == '1001')

Answer 2

const createTreeNodeFinder = (treeData) => {
  const memorizedNodes = new Map();

  const collect = (treeData, name) => {
    const path = [];
    const dummyRoot = {
      name: "",
      childs: treeData
    };

    const helper = (root, path) => {
      if (!root) return false;

      if (root.name && !memorizedNodes.has(root.name)) {
        memorizedNodes.set(root.name, root);
      }

      path.push(root);

      if (root.name === name) {
        return true;
      }

      for (let i = 0; i < root.childs.length; ++i) {
        root.childs[i]._parent = root;
        if (helper(root.childs[i], path)) return true;
      }

      path.pop();
    };

    helper(dummyRoot, path);
    path.shift();

    return path;
  };

  const collectNodeToRoot = (node) => {
    const res = [];

    let parent = node._parent;
    while (parent) {
      res.push(parent);
      parent = parent._parent;
    }

    //去掉dummyRoot
    res.pop();
    res.reverse();

    return res;
  };

  return (name) => {
    const node = memorizedNodes.get(name);

    if (!node) {
      console.log("slow path");
      return collect(treeData, name)?.[0].name ?? "";
    } else {
      console.log("fast path");
      return collectNodeToRoot(node)?.[0]?.name ?? "";
    }
  };
};

const finder = createTreeNodeFinder(tree);

console.log(finder("A"));
console.log(finder("1001"));
console.log(finder("1002"));
console.log(finder("1003"));
console.log(finder("B"));
console.log(finder("1004"));
console.log(finder("1005"));

Answer 3

function solution(list, target, level = 0, result) {
  for(item of list) {
    if (item.name === target) return level === 0 ? target : result

    if (Array.isArray(item.childs)) {
      result = level === 0 && !result ? item.name : result
      solution(item.childs, target, level + 1, result)
    }
  }

  return result
}

console.log('solution: ', solution(tree, 'A'));
console.log('solution: ', solution(tree, '1003'));