按给定的目标值对递归定义的树进行排序

Question

我们有一棵树，其中树中的每个节点都是一个对象，具有映射到非唯一整数的必需“val”属性和一个可选的“子节点”属性，如果存在，则映射到子节点数组。

此挑战涉及编写一个函数 priorityNodes(tree, targetVal)，它接受符合上述定义的有效嵌套树对象。该函数应将所有包含一个或多个具有 node.val === targetVal 节点的“子”数组排序到数组的前面。对于此输入，调用 priorityNodes(tree, 7)

的输出

输入

{
  "val": 1,
  "children": [
    {"val": 2},
    {
      "val": 3,
      "children": [
        {
          "val": 4,
          "children": [
            {"val": 5},
            {"val": 6},
            {"val": 7}
          ]
        }
      ]
    }
  ]
}

预期输出

{
  "val": 1,
  "children": [
    {
      "val": 3, // <-- moved up
      "children": [
        {
          "val": 4,
          "children": [
            {"val": 7}, // <-- moved up
            {"val": 5},
            {"val": 6}
          ]
        }
      ]
    },
    {"val": 2}
  ]
}

树中具有与目标匹配的值或子节点的每个节点都已移至其各自数组的前面。

非优先节点应保持其相对于彼此的原始相对顺序，移动到阵列前面的优先节点也应保持相对于阵列中其他优先节点的顺序。如果您愿意，除了返回参数树之外，您的函数还可以就地改变参数树。

这是我到目前为止得到的结果，我无法确定为什么它仍然不起作用，请问有人可以提供任何解决方案吗？

class Node {
    val;
    children;

    constructor(data) {
        this.val = data.val || null
        if(data.children?.length > 0){
            this.children = []
            this.addChildren(data.children)
        }else if(this.children?.length <= 0){
            delete this.children
        }
    }
    addChildren(children) {
        if(children?.length > 0){
            for (let i = 0; i < children.length; i++) {
                let newNode = new Node(children[i])
                this.children.push(newNode)
            }
        }
    }
}


function repeater(node, targetVal) {
    let parentFlag = false
    if(node.children?.length > 0){
        for (let i = 0; i < node.children.length; i++) {
            if(repeater(node.children[i], targetVal)){
                node.children.unshift(...node.children.splice(i, 1))
                parentFlag = true
            }
        }
    }
    return node.val === targetVal || parentFlag;
}

const prioritizeNodes = (oldtree, targetVal) => {
    if(!oldtree.children){
        return oldtree;
    }
    let tree = new Node(oldtree)
    for (let i = 0; i < oldtree.children.length; i++) {
        repeater(tree, targetVal)
    }
  console.log(tree)
    return tree;
}

Answer 1

将优先级节点转移到子数组中会颠倒优先级节点的顺序，这不是要求的。

我会避免突变并创建两个新的子数组，其中的子数组被划分：一个用于优先子数组，一个用于其他子数组。然后将这两个连接起来。让递归函数 return 新的子数组和标志。

代码：

function prioritizeNodes(tree, targetVal) {
    function recur({val, children}) {
        if (!children) {
            return [{ val }, val === targetVal];
        }
        let categories = [[], []], 
            isPrio;
        for (let child of children) {
            [child, isPrio] = recur(child);
            categories[1-isPrio].push(child);
        }
        return [
            { val, children: categories.flat() },
            categories[0].length > 0 || val === targetVal
        ];
    }
    return recur(tree)[0];
}

// Example input
let tree = {"val": 1,"children": [{"val": 2},{"val": 3,"children": [{"val": 4,"children": [{"val": 5},{"val": 6},{"val": 7}]}]}]}

let result = prioritizeNodes(tree, 7);
console.log(result);

按给定的目标值对递归定义的树进行排序

Sort recursively-defined tree by given target value

javascript

sorting

algorithm

tree