三元树路径

Question

我正在解决以下问题：

Given a ternary tree (each node of the tree has at most three children), find all root-to-leaf paths.

示例：

我的代码如下：

from __future__ import annotations

import itertools
from collections import deque, Iterable


class TernaryNode:
    def __init__(self, val: int) -> None:
        self.children: list[TernaryNode] = []
        self.val = val

    def __repr__(self) -> str:
        return str(self.val)


def ternary_tree_paths(root: TernaryNode) -> Iterable[Iterable[int]]:
    def _visit(node: TernaryNode) -> Iterable[deque[int]]:
        if not node:
            return []
        if not node.children:
            queue = deque()
            queue.append(node.val)
            return [queue]
        # **
        paths = itertools.chain.from_iterable(map(lambda ch: _visit(ch), node.children))
        for p in paths:
            p.appendleft(node.val)

        return paths

    return _visit(root)

如图所示，上面的代码返回一个空列表，其中所需的行为是[deque([1, 2, 3]), deque([1, 4]), deque([1, 6])]。注意带**的行；如果我将该行重写为paths = [p for ch in node.children for p in _visit(ch)]，它将按预期工作。我猜问题是因为函数from_iterable的计算是惰性的，但是当我迭代这些项时，它不应该被强制计算吗

Answer 1

在尝试对每个项执行appendleft时，您正在耗尽链iterable。之后paths为空

您需要确保iterable只计算一次：

def ternary_tree_paths(root: TernaryNode) -> Iterable[Iterable[int]]:
    def _visit(node: TernaryNode) -> Iterable[deque[int]]:
        if not node:
            return []
        if not node.children:
            queue = deque()
            queue.append(node.val)
            return [queue]
        paths = itertools.chain.from_iterable(map(_visit, node.children))
        retval = [] # to keep track of results
        for p in paths: # iterate
            p.appendleft(node.val)
            retval.append(p) # add to result

        return retval # return result

    return _visit(root)

这将产生：

[deque([1, 2, 3]), deque([1, 4]), deque([1, 6])]

例如问题中的例子