遞歸
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回二維列表霹琼，內部每個列表表示找到的路徑
def FindPath(self, root, expectNumber):
# write code here
result = []
path = []
self.path_method(root, result, path, expectNumber)
return result
def path_method(self, root, result, path, expectNumber):
if root:
path.append(root.val)
if not root.left and not root.right and sum(path) == expectNumber:
result.append([i for i in path])
self.path_method(root.left, result, path, expectNumber)
self.path_method(root.right, result, path, expectNumber)
path.pop()
root = TreeNode(10)
mid = TreeNode(5)
root.left = mid
root.right = TreeNode(12)
mid.left = TreeNode(4)
mid.right = TreeNode(7)
s = Solution()
print(s.FindPath(root, 22))
非遞歸
class Solution:
# 返回二維列表流译，內部每個列表表示找到的路徑
def FindPath(self, root, expectNumber):
# write code here
result = []
stack = []
pre = None
while stack or root:
if root:
stack.append(root)
temp = [i.val for i in stack]
if not root.left and not root.right and sum(temp) == expectNumber:
result.append(temp)
root = root.left
else:
temp_node = stack[-1]
if temp_node.right and temp_node.right != pre:
root = temp_node.right
else:
pre = stack.pop()
return result
