V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
cochlea
V2EX  ›  编程

二叉树剪切的一个题目,不知掉如何解

  •  
  •   cochlea · 191 天前 · 1275 次点击
    这是一个创建于 191 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目要求为,给定一个树和 target ,找出所有满足 target 的所有树,剩余树全部被删除。 其中要求使用广度遍历的形式来完成,且对于最后一个节点如果超出只删除超出部分。

    例如 target 为 200 ,root = 100 ,children1 = 80 ,children2 = 80 ,则返回 root ,children1 和被裁剪的 childrn2 20 的值。

    如果小于 target 则全部返回。

    8 条回复    2024-04-27 15:29:26 +08:00
    Philippa
        1
    Philippa  
       191 天前 via iPhone
    广度遍历非常标准化了,拿个 stack 或 queue 每层收集,然后 loop 每一层判断就可以了。
    MeiJiayun
        2
    MeiJiayun  
       191 天前 via iPhone
    实现可以看下回溯模板,用回溯算法实现思路会比较清晰些
    geelaw
        3
    geelaw  
       191 天前 via iPhone
    我看了例子之后还是不能理解题目在说什么。例子里 target 是 200 ,什么叫做“满足 200 的树”?什么叫“剩余树”?题目不是说“给定一个树”吗?

    另外那个东西叫“广度优先遍历”,但在二叉树通常不这么说,因为二叉树的子节点是有序的,要指定先访问左子节点还是右子节点才能确定惟一的序,除非你不在意序(比如把二叉树当成普通的有根树)。
    cochlea
        4
    cochlea  
    OP
       191 天前
    @Philippa 主要是需要删除掉所有不符合的条件,以及对于不满足的子树还要剪切,感觉写的一点头绪都没😭
    Helsing
        5
    Helsing  
       191 天前 via iPhone
    不知所云,连题目都没说不清楚
    cochlea
        6
    cochlea  
    OP
       191 天前
    @geelaw 抱歉抱歉,表达的有点乱,其实就是无序的树。之所以假定广度优先遍历是因为,例如下面这个结构
    100
    40 80
    20 20 20 20

    target 为 150 ,我期待是得到这样的值
    100
    40 20 ( 80 - 60 )
    geelaw
        7
    geelaw  
       191 天前 via iPhone
    @cochlea #6 那为什么不期待

    100
    (删除) 50 (=80-30)

    呢?我现在大概理解你想说的是:输入一个每个节点上标记了正数的二叉树(或者可能是指每个节点最多有两个子节点的有根树)和一个正数 target (不清楚如何处理 0 ),按照某种顺序(不清楚你想要的是什么顺序,但看起来满足:a 和 b 的顺序是距离根越近则越先访问,距离相等且 a 和 b 不是同一个节点的子节点,则 a 和 b 的顺序同于两者祖先的顺序)遍历该二叉树的所有节点,在已经访问节点之和首次不小于 target 时停止,删去还未访问的节点,并把最后访问的节点的数修改使已访问的节点之和等于 target 。

    这个理解如果正确,填上合适的细节,怎么写代码就很明显了。但我依然不理解什么叫“所有满足……的所有树”,因为按照上面这个理解答案只可能是一棵树,何来“所有”?我的建议是先把想法用母语(比如汉语)表达,再翻译成代码。
    codevn
        8
    codevn  
       191 天前
    ```
    class TreeNode {
    constructor(value = 0, children = []) {
    this.value = value;
    this.children = children;
    }
    }

    function trimTree(root, target) {
    if (!root) return null;

    let queue = [root];
    let result = new TreeNode(root.value);
    let resultQueue = [result];
    let currentSum = root.value;

    while (queue.length > 0) {
    let currentNode = queue.shift();
    let resultNode = resultQueue.shift();

    let childrenSum = 0;
    let tempChildren = [];

    for (let child of currentNode.children) {
    queue.push(child);
    childrenSum += child.value;
    let newChild = new TreeNode(child.value);
    tempChildren.push(newChild);
    resultQueue.push(newChild);
    }

    if (currentSum + childrenSum <= target) {
    resultNode.children = tempChildren;
    currentSum += childrenSum;
    } else {
    let remaining = target - currentSum;
    resultNode.children = [];
    for (let child of tempChildren) {
    if (child.value <= remaining) {
    resultNode.children.push(child);
    remaining -= child.value;
    } else {
    child.value = remaining;
    resultNode.children.push(child);
    break;
    }
    }
    break;
    }
    }

    return result;
    }

    // 示例
    let child1 = new TreeNode(80);
    let child2 = new TreeNode(80);
    let root = new TreeNode(100, [child1, child2]);

    let trimmedTree = trimTree(root, 200);
    console.log(trimmedTree);

    ```
    这意思么?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   973 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 22:04 · PVG 06:04 · LAX 14:04 · JFK 17:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.