目录
任务
112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。叶子节点 是指没有子节点的节点。
思路
这道题非常的有典型性，首先，它和路径有关，根据昨天所学习的，路径相关的问题可以按照先序遍历树，然后添加节点进路径中，适当时需要回溯，即利用了遍历法。另外，此题的题意可以转化为：已经累计了sum,剩余的值相加是否可以达到target,左子树中是否有这样的路径，右子树中是否有这样的路径，这个思路又用了传统递归的逻辑。即一道题用了之前提到的两种思路。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def __init__(self):
self.sum = 0
def hasPathSum(self, root, targetSum):
"""
:type root: TreeNode
:type targetSum: int
:rtype: bool
"""
return self.dfs(root,targetSum)
def dfs(self,node,target):
if not node:return False
self.sum += node.val #第一次访问节点时做路径和累加
if not node.left and not node.right: # 到叶子判断是否符合条件
if self.sum == target:
return True
else: return False
else: # 对于普通节点，
lres = False
rres = False
if node.left:
lres = self.dfs(node.left,target)
self.sum -= node.left.val
if node.right:
rres = self.dfs(node.right,target)
self.sum -= node.left.val
return lres or rres
####else中的代码可以优化成下面这样
# if node.left:
# if self.dfs(node.left,target): return True
# self.sum -= node.left.val
# if node.right:
# if self.dfs(node.right,target): return True
# self.sum -= node.right.val
# return False
或者将sum作为参数传递，由于int是不可变类型，所以改为参数后，相当于局部变量，就不需要显式回溯了。
class Solution(object):
def hasPathSum(self, root, targetSum):
"""
:type root: TreeNode
:type targetSum: int
:rtype: bool
"""
return self.dfs(root,targetSum,0)
def dfs(self,node,target,sum):
if not node:return False
sum += node.val #第一次访问节点时做路径和累加
if not node.left and not node.right: # 到叶子判断是否符合条件
if sum == target:
return True
else: return False
else: # 对于普通节点，找了了就返回True，都没找到才返回False
if node.left:
if self.dfs(node.left,target,sum): return True
if node.right:
if self.dfs(node.right,target,sum): return True
return False
实际上，上述代码还可以优化，即不需要sum变量，只需要Target变量在到达叶子时为0即可。
class Solution(object):
def hasPathSum(self, root, targetSum):
"""
:type root: TreeNode
:type targetSum: int
:rtype: bool
"""
return self.dfs(root,targetSum)
def dfs(self,node,target):
if not node:return False
target -= node.val #第一次访问节点时用目标值减去节点值
if not node.left and not node.right: # 到叶子判断是否符合条件
if 0 == target:
return True
else: return False
else: # 对于普通节点，找了了就返回
if node.left:
if self.dfs(node.left,target): return True
if node.right:
if self.dfs(node.right,target): return True
return False
113. 路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
思路
这道题看起来比上题难，要收集所有路径，上题只要找到一个返回True就行，实际上，该题的思路比上题简单的多。
由于是收集路径，我们只要遍历过程中，append列表，到叶子节点时，收集符合条件的路径就行。另外，由于path是参数和可变类型变量，因此归的时候需要回溯。并且，由于path可变类型和参数，所以加入到paths中时需要用其副本,避免被后续path的修改影响。
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
path = []
paths = []
self.dfs(root,targetSum,0,path,paths)
return paths
def dfs(self,node,target,sum,path,paths):
if not node: return []
sum += node.val
path.append(node.val)
if not node.left and not node.right: #到达叶子节点，收集路径
if sum == target:
paths.append(path[:])
# 普通节点继续向左右递归遍历
if node.left:
self.dfs(node.left,target,sum,path,paths)
if node.right:
self.dfs(node.right,target,sum,path,paths)
path.pop() # 回溯
用局部变量隐式回溯的方法
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
path = []
paths = []
self.dfs(root,path,paths)
return paths
def dfs(self,node,path,paths):
if not node: return
print(path)
new_path = path[:] + [node.val]
if not node.left and not node.right:
paathStr = '->'.join(map(str,new_path))
paths.append(paathStr)
self.dfs(node.left,new_path,paths)
self.dfs(node.right,new_path,paths)
106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。inorder 和 postorder 都由 不同 的值组成
思路
根据后序数组的最后一个数建立树根，找到其在中序数组中的位置，这个位置将中序数组分为了，左中右，根据区间长度（左，右），将后序数组也分为了左右中，接着，递归的建立树根的左右子树,返回即可，这里要注意的是区间正确。
# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if len(postorder) == 0:
return None
rootVal = postorder[-1] # 根据后序数组的最后一数创建一个节点，即为中间节点
root = TreeNode(rootVal)
index = 0
while index < len(inorder):
if inorder[index] == rootVal:
break
index+=1
leftInOrder = inorder[:index] # 左闭右开区间
rightInOrder = inorder[index+1:len(inorder)]
leftPostOrder = postorder[:index]
rightPostOrder = postorder[index:len(inorder)-1]
root.left = self.buildTree(leftInOrder,leftPostOrder)
root.right = self.buildTree(rightInOrder,rightPostOrder)
return root
105. 从前序与中序遍历序列构造二叉树
思路
修改下区间的定义即可，与上题基本一致。
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if len(preorder) == 0:
return None
rootVal = preorder[0] # 根据前序数组的第一数创建一个节点，即为中间节点
root = TreeNode(rootVal)
print(rootVal)
index = 0
while index < len(inorder):
if inorder[index] == rootVal:
break
index+=1
leftInOrder = inorder[:index] # 左闭右开区间
rightInOrder = inorder[index+1:len(inorder)]
leftPreOrder = preorder[1:index+1]
rightPreOrder = preorder[index+1:len(inorder)]
root.left = self.buildTree(leftPreOrder,leftInOrder)
root.right = self.buildTree(rightPreOrder,rightInOrder)
return root
心得体会
今天的题目中，路经总和非常具有典型性，包含了之前学习的遍历和递归的两种思路.
路径总和II 练习了遍历的思路。
也给除了很多解法（局部变量（不可变类型参数，函数内局部变量），全局变量（成员变量，可变类型参数），隐式回溯，显示回溯），需要细细体会。