I
描述
给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。
一个有效的路径，指的是从根节点到叶节点的路径。
样例
给定一个二叉树，和 目标值 = 5:
1
/ \
2 4
/
2 3
返回：
[
[1, 2, 2],
[1, 4]
]
代码
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of binary tree.
@return: An integer
"""
def maxPathSum(self, root):
# write your code here
self.maxPath = root.val
self.Dfs(root)
return self.maxPath
def Dfs(self, root):
# TODO: write code...
if root is None:
return 0
left = max(0, self.Dfs(root.left))
right = max(0, self.Dfs(root.right))
leap = left + root.val + right
if leap > self.maxPath:
self.maxPath = leap
return max(left + root.val, right + root.val)
题目来源
https://www.lintcode.com/problem/binary-tree-path-sum-i/description
II
描述
给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）
样例
给出一棵二叉树：
1
/ \
2 3
返回 6
代码
这个写法性能差一点。
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param: root: the root of binary tree
@param: target: An integer
@return: all valid paths
"""
def binaryTreePathSum2(self, root, target):
# write your code here
self.result = []
if root is None:
return self.result
self.target = target
local = []
self.Dfs(root, 0, local)
return self.result
def Dfs(self, root, sumPath, local):
if root is None:
return
local.append(root.val)
sumPath += root.val
if sumPath == self.target:
self.result.append(list(local))
new_local = local[:]
sumPath_local = sumPath
while(len(new_local)>1):
sumPath_local -= new_local[0]
del new_local[0]
if sumPath_local == self.target:
self.result.append(list(new_local))
self.Dfs(root.left, sumPath, local)
self.Dfs(root.right, sumPath, local)
local.pop()
这个代码的性能要好一些，但是算法都一样。
class Solution:
"""
@param: root: the root of binary tree
@param: target: An integer
@return: all valid paths
"""
def binaryTreePathSum2(self, root, target):
# write your code here
self.result = []
if root is None:
return self.result
self.target = target
local = []
self.Dfs(root, 0, local)
return self.result
def Dfs(self, root, sumPath, local):
if root is None:
return
local.append(root.val)
sumPath += root.val
if sumPath == self.target:
self.result.append(list(local))
for i in range(1, len(local)):
new_local = local[i:len(local)]
print(new_local)
if sum(new_local) == self.target:
self.result.append(list(new_local))
self.Dfs(root.left, sumPath, local)
self.Dfs(root.right, sumPath, local)
local.pop()
到达每个子节点都有一个“回头观测”的过程，
for i in range(1, len(local)):
new_local = local[i:len(local)]
print(new_local)
if sum(new_local) == self.target:
self.result.append(list(new_local))
把先进入的节点依次撇除然后再计算是否符合结果。
题目来源
https://www.lintcode.com/problem/binary-tree-path-sum-ii/description
网友评论