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

[cochlea]

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

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

如果小于 target 则全部返回。

[Philippa]

广度遍历非常标准化了，拿个 stack 或 queue 每层收集，然后 loop 每一层判断就可以了。

[MeiJiayun]

实现可以看下回溯模板，用回溯算法实现思路会比较清晰些

[geelaw]

我看了例子之后还是不能理解题目在说什么。例子里 target 是 200 ，什么叫做“满足 200 的树”？什么叫“剩余树”？题目不是说“给定一个树”吗？

另外那个东西叫“广度优先遍历”，但在二叉树通常不这么说，因为二叉树的子节点是有序的，要指定先访问左子节点还是右子节点才能确定惟一的序，除非你不在意序（比如把二叉树当成普通的有根树）。

[cochlea]

@Philippa 主要是需要删除掉所有不符合的条件，以及对于不满足的子树还要剪切，感觉写的一点头绪都没😭

[Helsing]

不知所云，连题目都没说不清楚

[cochlea]

@geelaw 抱歉抱歉，表达的有点乱，其实就是无序的树。之所以假定广度优先遍历是因为，例如下面这个结构
100
40 80
20 20 20 20

target 为 150 ，我期待是得到这样的值
100
40 20 （ 80 - 60 ）

[geelaw]

@cochlea #6 那为什么不期待

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

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

这个理解如果正确，填上合适的细节，怎么写代码就很明显了。但我依然不理解什么叫“所有满足……的所有树”，因为按照上面这个理解答案只可能是一棵树，何来“所有”？我的建议是先把想法用母语（比如汉语）表达，再翻译成代码。

[codevn]

```
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);

```
这意思么？