07-01：数据类型二：二叉树：路径和问题
递归是一个太强大的算法了！
总结一下：路径和这个利用递归遍历所有可能性！
一共四道题
1、节点和为固定值是否存在
二叉树中是否存在节点和为指定值的路径
class Solution:
def hasPathSum(self , root , sum ):
# write code here
if not root:
return False
if root.val==sum and not root.left and not root.right:
return True
return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=196&&tqId=37053&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
2、节点和为固定值的路径
二叉树根节点到叶子节点和为指定值的路径
class Solution:
def pathSum(self , root , sum ):
ret = list()
path = list()
def dfs(root, target):
if not root:
return
path.append(root.val)
target -= root.val
if not root.left and not root.right and target == 0:
ret.append(path[:])
dfs(root.left, target)
dfs(root.right, target)
path.pop()
#在回溯呀
dfs(root, sum)
return ret
https://www.nowcoder.com/practice/840dd2dc4fbd4b2199cd48f2dadf930a?tpId=117&&tqId=37718&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
3、所有节点的路径和
二叉树根节点到叶子节点的所有路径和
class Solution:
def sumNumbers(self , root ):
# write code here
if not root:
return 0
def preorder(root,sum1):
if not root:
return 0
sum1=10*sum1+root.val
if not root.left and not root.right:
return sum1
return preorder(root.left,sum1)+preorder(root.right,sum1)
#这样可以求出所有路径和啊
return preorder(root,0)
https://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83?tpId=117&&tqId=37715&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
4、最大路径和
二叉树的最大路径和
class Solution:
def maxPathSum(self , root ):
# write code here
self.res=float('-inf')
def pathmax(root):
if not root:
return 0
leftmax=max(0,pathmax(root.left))
rightmax=max(0,pathmax(root.right))
self.res=max(self.res,leftmax+rightmax+root.val)
#全局最大
return max(leftmax,rightmax)+root.val
#包含当前节点的最大值
if not root:
return 0
pathmax(root)
return self.res
https://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a?tpId=196&&tqId=37050&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
