题目要求为,给定一个树和 target ,找出所有满足 target 的所有树,剩余树全部被删除。 其中要求使用广度遍历的形式来完成,且对于最后一个节点如果超出只删除超出部分。
例如 target 为 200 ,root = 100 ,children1 = 80 ,children2 = 80 ,则返回 root ,children1 和被裁剪的 childrn2 20 的值。
如果小于 target 则全部返回。
1
Philippa 191 天前 via iPhone
广度遍历非常标准化了,拿个 stack 或 queue 每层收集,然后 loop 每一层判断就可以了。
|
2
MeiJiayun 191 天前 via iPhone
实现可以看下回溯模板,用回溯算法实现思路会比较清晰些
|
3
geelaw 191 天前 via iPhone
我看了例子之后还是不能理解题目在说什么。例子里 target 是 200 ,什么叫做“满足 200 的树”?什么叫“剩余树”?题目不是说“给定一个树”吗?
另外那个东西叫“广度优先遍历”,但在二叉树通常不这么说,因为二叉树的子节点是有序的,要指定先访问左子节点还是右子节点才能确定惟一的序,除非你不在意序(比如把二叉树当成普通的有根树)。 |
5
Helsing 191 天前 via iPhone
不知所云,连题目都没说不清楚
|
6
cochlea OP @geelaw 抱歉抱歉,表达的有点乱,其实就是无序的树。之所以假定广度优先遍历是因为,例如下面这个结构
100 40 80 20 20 20 20 target 为 150 ,我期待是得到这样的值 100 40 20 ( 80 - 60 ) |
7
geelaw 191 天前 via iPhone
@cochlea #6 那为什么不期待
100 (删除) 50 (=80-30) 呢?我现在大概理解你想说的是:输入一个每个节点上标记了正数的二叉树(或者可能是指每个节点最多有两个子节点的有根树)和一个正数 target (不清楚如何处理 0 ),按照某种顺序(不清楚你想要的是什么顺序,但看起来满足:a 和 b 的顺序是距离根越近则越先访问,距离相等且 a 和 b 不是同一个节点的子节点,则 a 和 b 的顺序同于两者祖先的顺序)遍历该二叉树的所有节点,在已经访问节点之和首次不小于 target 时停止,删去还未访问的节点,并把最后访问的节点的数修改使已访问的节点之和等于 target 。 这个理解如果正确,填上合适的细节,怎么写代码就很明显了。但我依然不理解什么叫“所有满足……的所有树”,因为按照上面这个理解答案只可能是一棵树,何来“所有”?我的建议是先把想法用母语(比如汉语)表达,再翻译成代码。 |
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); ``` 这意思么? |