一、学习视频
【看到递归就晕？带你理解递归的本质！】 https://www.bilibili.com/video/BV1UD4y1Y769/?share_source=copy_web&vd_source=dc0e55cfae3b304619670a78444fd795
二、视频跟练代码
方法均来自视频
（1）递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val #储存节点值
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
#递归
if root is None: #None要使用is，不能使用==
return 0
ldepth = self.maxDepth(root.left)
rdepth = self.maxDepth(root.right)
return max(ldepth,rdepth) + 1 #加上当前节点（2）递归+全局变量(准确来说是非局部)
关于nonlocal关键字的相关知识可见我的文章：http://t.csdnimg.cn/hfIpU
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val #储存节点值
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
#递归+全局变量(准确来说是非局部)
ans = 0
def f(node,cnt):
if node is None:
return
cnt += 1
nonlocal ans
ans = max(ans,cnt)
f(node.left,cnt) #遍历左右子树
f(node.right,cnt)
f(root,0)
return ans时空复杂度均为O(n)。储存节点使用栈。
三、课后作业练习
（1）递归+非局部变量
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
#递归+非局部变量
ans = 100000
def f(node,cnt):
nonlocal ans
if node is None or cnt >= ans:
#为空或大于等于最小深度时返回
return
cnt += 1
if node.left is None and node.right is None:
#在为叶子节点时更新并返回
ans = min(ans,cnt)
return
f(node.left,cnt)
f(node.right,cnt)
f(root,0)
return 0 if ans > 10000 else ans(2)直接递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
#递归
if root is None:
return 0
ldepth = self.minDepth(root.left)
rdepth = self.minDepth(root.right)
if ldepth == 0 or rdepth == 0:
#为叶子节点返回1，0+1
#不为叶子节点但一侧为空，返回不为空+1
return max(ldepth,rdepth) + 1
else:
#两侧均不为空，返回小值+1
return min(ldepth,rdepth) + 1递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
#递归
if root is None:
return False
if root.left is None and root.right is None:
#叶子节点值是不是target
#到达边界，开始归
return root.val == targetSum
#左右路径和是不是targetSum-root.val
leftbool = self.hasPathSum(root.left,targetSum-root.val)
rightbool = self.hasPathSum(root.right,targetSum-root.val)
return leftbool or rightbool递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
#递归
if root is None:
return []
if root.left is None and root.right is None and root.val == targetSum:
#表示这条路有一条可行路即为[root.val]，如[[~],[~]]即为两条可行路
return [[root.val]]
leftlst = self.pathSum(root.left,targetSum-root.val)
rightlst = self.pathSum(root.right,targetSum-root.val)
all_lst = leftlst + rightlst #将左右可行路汇总
for lst in all_lst: #在可行路前加上当前节点，没可行路不参与循环
lst.insert(0,root.val)
return all_lst（1）递归+字符串。比较麻烦。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
# 递归，有根节点
def f(node) -> List[str]:
if node is None:
return []
if node.left is None and node.right is None:
return [f'{node.val}']
leftList = f(node.left)
rightList = f(node.right)
allList = leftList + rightList
ans = []
for s in allList:
ans.append(f'{node.val}'+s)
return ans
strnums = f(root)
s = 0
for num in strnums:
s += int(num)
return s（2）递归+数学 。方法来自题解（. - 力扣（LeetCode））。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
#递归+数学
def f(node,temp) -> int:
if node is None:
return 0
temp = 10 * temp + node.val #在递的时候进行操作
if node.left is None and node.right is None:
return temp #在叶子节点返回递的值
l = f(node.left,temp)
r = f(node.right,temp)
return l+r
return f(root,0)之前有一点这种想法，但是没有实现。只局限在了在归的时候进行操作，而没有想到在递的时候进行操作。
递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
#递归
if root is None:
return []
if root.left is None and root.right is None:
return [f"{root.val}"] #只能从叶子节点开始记录
leftStrList = self.binaryTreePaths(root.left)
rightStrList = self.binaryTreePaths(root.right)
all_StrList = leftStrList + rightStrList #左右路径汇总
ans = []
for s in all_StrList:
ans.append(f'{root.val}->' + s) #添加当前节点
return ans（未完待续）
感谢你看到这里！一起加油吧！
