Python3实现二叉树路径查找：按层构建与左优先遍历

桃夭

发布时间：2026-10-13 | 6人浏览过

原创

本文介绍如何使用Python3实现二叉树中所有和为特定值的路径查找。首先通过按层从左到右的顺序构建二叉树，随后采用左子树优先的深度优先搜索策略遍历节点。文章包含完整的Node与Tree类定义，以及Solution递归算法，并提供了具体的输入输出样例及代码实现，帮助开发者理解树结构构建与路径搜索的结合应用。

二叉树路径查找问题描述

编写一个程序，用于创建一棵二叉树，并依据特定规则输出从根节点到叶子节点的所有路径。

具体的处理规则如下：

1. 计算从最顶端根节点到最底层叶子节点路径上所有节点值的总和。若该总和等于预设的目标值，则输出该路径上的所有节点。

2. 在从根节点遍历树的过程中，必须遵循从左到右的顺序，即优先访问左子树的节点。

二叉树构建规则

二叉树的构建规则为：从上至下、逐层进行，且在同一层内按照从左到右的顺序依次构造节点。

当输入值为"10,5,12,4,7"时，构造出的树结构如下所示：

1） 10 2） 10 / 5

3） 10 /\ 5 12 4） 10 /\ 5 12 / 4

5） 10 /\ 5 12 /\ 4 7

路径查找逻辑与示例

针对上述构建的二叉树，假设当前设置的“路径和”目标值为19，则输出结果为： 10,5,4

若存在多条满足条件的路径，需按照从左到右的遍历顺序生成结果，每行显示一条路径。例如，当设置的“路径和”为22时：

输出结果为：

10,5,7 10,12

如果在遍历结束后未找到和为设定值的路径，则输出“error”。

输入输出格式规范

三、输入格式说明：

第一行输入整数N，表示目标路径和。第二行输入一个字符串，包含多个正整数，各数字之间使用逗号“,”分隔。

四、输出要求：

五、样例输入：

22 10,5,12,4,7

六、样例输出：

10,5,7 10,12

demo：

Python3完整代码实现


class Node(object):
  def __init__(self, x):
   self.val = x
   self.left = None
   self.right = None
class Tree(object):
 lt = [] # 依次存放左右孩子未满的节点
 def __init__(self):
   self.root = None
 def add(self, number):
   node = Node(number) # 将输入的数字节点化，使其具有左右孩子的属性
   if self.root == None:
     self.root = node
     Tree.lt.append(self.root)
   else:
     while True:
       point = Tree.lt[0] # 依次对左右孩子未满的节点分配孩子
       if point.left ==None:
         point.left = node
         Tree.lt.append(point.left) # 该节点后面作为父节点也是未满的，也要加入到列表中。
         return
       elif point.right ==None:
         point.right = node
         Tree.lt.append(point.right) # 与左孩子同理
         Tree.lt.pop(0) # 表示该节点已拥有左右孩子，从未满列表中去除
         return
class Solution:
 def __init__(self):
   self.results = []
 def RecursionFindPath(self, root, expectNumber, result):
   result.append(root.val)
   if root.left == None and root.right == None and sum(result) == expectNumber:
     self.results.append(result)
   temp = result[:]
   if root.left:
     self.RecursionFindPath(root.left, expectNumber, result)
   result = temp[:]
   if root.right:
     self.RecursionFindPath(root.right, expectNumber, result)
 def FindPath(self, root, expectNumber):
   if root == None:
     return []
   self.RecursionFindPath(root, expectNumber, [])
   self.results = sorted(self.results, key=len, reverse=True)
   return self.results
if __name__ =='__main__':
 t = Tree() # 二叉树类的实例化
 L = [10, 5, 12, 4, 7]
 for i in L:
   t.add(i)
 expectNum = 22
 print(Solution().FindPath(t.root, expectNum))

输出样例：