求可打印树中所有根到叶子路径的函数或算法

给定一棵层级结构的树，需要实现函数/算法输出所有从根节点到叶子节点的完整路径，预期输出如下：

1->2->4->8->16
1->2->4->8->17
1->2->4->8->16  # 注：原输出此处疑似笔误，实际应为对应叶子节点的路径
1->2->4->9->18
1->2->4->9->19
1->2->5->10->20
1->2->5->10->21
1->2->5->11->22
1->2->5->11->23
1->3->6->12->24
1->3->6->12->25
1->3->6->13->26
1->3->6->13->27
1->3->7->14->28
1->3->7->14->29
1->3->7->15->30
1->3->7->15->31

实现思路 #

采用**深度优先搜索（DFS）**递归方式：

• 维护当前路径列表，记录从根到当前节点的所有节点值
• 遍历当前节点的所有子节点，将子节点值加入路径后递归处理
• 遇到叶子节点（无任何子节点）时，将当前路径格式化为->连接的字符串并输出
• 递归返回时移除当前节点（回溯），保证路径的正确性

代码示例（Python） #

首先定义树节点结构：

class TreeNode:
    def __init__(self, val=0, children=None):
        self.val = val
        self.children = children if children is not None else []

实现路径打印函数：

def print_all_paths(root):
    def dfs(node, current_path):
        current_path.append(str(node.val))
        # 判定叶子节点
        if not node.children:
            print('->'.join(current_path))
        else:
            # 递归处理所有子节点
            for child in node.children:
                dfs(child, current_path)
        # 回溯
        current_path.pop()
    
    if root:
        dfs(root, [])

测试验证 #

按给定树结构构建节点并调用函数：

# 构建叶子节点
leaf16 = TreeNode(16)
leaf17 = TreeNode(17)
leaf18 = TreeNode(18)
leaf19 = TreeNode(19)
leaf20 = TreeNode(20)
leaf21 = TreeNode(21)
leaf22 = TreeNode(22)
leaf23 = TreeNode(23)
leaf24 = TreeNode(24)
leaf25 = TreeNode(25)
leaf26 = TreeNode(26)
leaf27 = TreeNode(27)
leaf28 = TreeNode(28)
leaf29 = TreeNode(29)
leaf30 = TreeNode(30)
leaf31 = TreeNode(31)

# 构建第四层节点
node8 = TreeNode(8, [leaf16, leaf17])
node9 = TreeNode(9, [leaf18, leaf19])
node10 = TreeNode(10, [leaf20, leaf21])
node11 = TreeNode(11, [leaf22, leaf23])
node12 = TreeNode(12, [leaf24, leaf25])
node13 = TreeNode(13, [leaf26, leaf27])
node14 = TreeNode(14, [leaf28, leaf29])
node15 = TreeNode(15, [leaf30, leaf31])

# 构建第三层节点
node4 = TreeNode(4, [node8, node9])
node5 = TreeNode(5, [node10, node11])
node6 = TreeNode(6, [node12, node13])
node7 = TreeNode(7, [node14, node15])

# 构建第二层节点
node2 = TreeNode(2, [node4, node5])
node3 = TreeNode(3, [node6, node7])

# 根节点
root = TreeNode(1, [node2, node3])

# 打印所有路径
print_all_paths(root)

运行后将输出符合预期的路径（修正原输出中的疑似笔误）

内容的提问来源于stack exchange，提问作者Kaheel Kaheel