python递归实现二叉树路径求和

该博客为学习笔记，记录学习心得，有错误的地方，一起探讨学习。

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

              5
             / 
            4   8
           /   / 
          11  13  4
         /      / 
        7    2  5   1

该题可通过递归算法实现。在求解之前，我们先来看看递归算法本质，递归算法实现可总结为两部分：
1.重复步骤
2.执行函数
先来看看斐波那契数列实现

def Fibonacci(n):
  	if n <= 1: #执行函数
          return n
  	return Fibonacci(n-1) + Fibonacci(n-2) #重复步骤
 
 for i in range(1, 20):
    print(Fibonacci(i), end=' ')
#输出
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 

来看看Fibonacci(n)流程
$$f(5)=f(4)+f(3)$$
$$f(5)=f(3)+f(2)+f(2)+f(1)$$
注意根据执行函数的执行条件：
$$f(2)=f(1)$$
所以
$$f(5)=f(1)+f(1)+f(1)+f(1)+f(1)+f(1)=5$$

现在我们来分析怎么用递归解答二叉树路径求和问题：
第一，找到递归部分：二叉树的每个节点结构是相同的。如下，重复调用TreeNode

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

因此我们考虑递归遍历每个节点

def dfs(node, curr_sum, s, res):
            if node.left: #从节点左边开始遍历
                dfs(node.left, curr_sum + [node.left.val], s, res)
            if node.right:#从节点右边边开始遍历
                dfs(node.right, curr_sum + [node.right.val], s, res)

第二，执行函数：这里执行函数有两个：
第一个是递归遍历每个节点，并把节点值保存，不像Fibonacci需要遍历到f(1)才执行

 curr_sum + [node.left.val]
curr_sum + [node.right.val],

第二个是终止条件，遍历到叶子节点，停止遍历，判断是否满足求和条件，满足，则储存结果

if not node.left and not node.right and sum(curr_sum) == s :
		 res.append(curr_sum)

最后完整代码如下（参考leecode官网题解）

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def pathSum(self, root,s):
        if not root:
            return []
        def dfs(node, curr_sum, s, res):
            if not node.left and not node.right and sum(curr_sum) == s : 
                res.append(curr_sum)
            if node.left:
                dfs(node.left, curr_sum + [node.left.val], s, res)
            if node.right:
                dfs(node.right, curr_sum + [node.right.val], s, res)
        curr_sum, res = [], []
        dfs(root, [root.val], s, res)
        return res

#插入数据
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)
#输出结果是：
[[5, 4, 11, 2], [5, 8, 4, 5]]

最后

以上就是故意朋友为你收集整理的python递归实现二叉树路径求和的全部内容，希望文章能够帮你解决python递归实现二叉树路径求和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。