输入一颗二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。路径定义为从树的根节点开始往下一直到叶节点所经过的节点形成一条路径
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def findPath(root, n):
if not root:
return []
result = []
def findPath2(root, path, currentNum):
currentNum += root.val
path.append(root)
# 判断root是否为叶子节点
flag = root.left == None and root.right == None
if currentNum == n and flag:
onepath = []
for node in path:
onepath.append(node.val)
result.append(onepath)
if currentNum < n:
if root.left:
findPath2(root.left, path, currentNum)
if root.right:
findPath2(root.right, path, currentNum)
path.pop()
findPath2(root, [], 0)
return result
root = TreeNode(1)
left = TreeNode(2)
right = TreeNode(3)
root.left = left
root.right = right
left1 = TreeNode(4)
right1 = TreeNode(5)
right.left = left1
right.right1 = right1
left2 = TreeNode(6)
left1.left = left2
left3 = TreeNode(11)
left.left = left3
'''
1
2 3
4 5
6
'''
print(findPath(root, 14))
[[1, 2, 11], [1, 3, 4, 6]]
正文完