用python计算二叉树路径之和

墨蓝 2024-02-25 03:00 36阅读 0赞

**问题**

给定一个二叉树和一个目标，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

**方法**

1.  使用递归函数：
    
    二叉树每个节点结构是相同的。
2.  执行递归函数遍历每一个节点，并把节点保存。
3.  遍历到叶子节点，停止遍历，判断是否满足求和条件。

代码清单 1

<table> 
 <tbody> 
 <tr> 
 <td>class TreeNode(object): &nbsp; &nbsp;def __init__(self, x): &nbsp; &nbsp; &nbsp; &nbsp;self.val = x &nbsp; &nbsp; &nbsp; &nbsp;self.left = None &nbsp; &nbsp; &nbsp; &nbsp;self.right = None class Solution(object): &nbsp; &nbsp;def pathSum(self, root,s): &nbsp; &nbsp; &nbsp; &nbsp;if not root: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return [] &nbsp; &nbsp; &nbsp; &nbsp;def dfs(node, curr_sum, s, res): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if not node.left and not node.right and sum(curr_sum) == s : &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;res.append(curr_sum) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if node.left: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;dfs(node.left, curr_sum + [node.left.val], s, res) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if node.right: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;dfs(node.right,curr_sum + [node.right.val], s, res) &nbsp; &nbsp; &nbsp; &nbsp;curr_sum, res = [], [] &nbsp; &nbsp; &nbsp; &nbsp;dfs(root, [root.val], s, res) &nbsp; &nbsp; &nbsp; &nbsp;return res &nbsp; #插入数据 root = TreeNode(5) l1 = TreeNode(4) r1 = TreeNode(8) root.left = l1 root.right = r1 l2 = TreeNode(11) r2 = TreeNode(13) r3 = TreeNode(4) l1.left = l2 r1.left = r2 r1.right = r3 l3 = TreeNode(7) l4 = TreeNode(2) r4 = TreeNode(5) r5 = TreeNode(1) l2.left = l3 l2.right = l4 r3.left = r4 r3.right = r5 solution = Solution() t = solution.pathSum(root,22) print(t)</td> 
 </tr> 
 </tbody> 
</table>

**结语**

针对此类用递归实现二叉树路径求和的问题，使用递归算法来实现二叉树路径求和的问题，提出递归算法遍历每一个节点的方法，通过以上实验，证明该方法是有效的，本文的仍有方法不足或考虑不周的地方，求二叉树路径总和有各种各样的方法，并不局限于此，未来可以继续研究更加高级简便的方法。