[关闭]
@liweiwei1419 2019-02-10T15:12:57.000000Z 字数 1468 阅读 1107

LeetCode 第 113题:路径总和 II

二叉树 深度优先遍历


标签(空格分隔): 二叉树 深度优先遍历


传送门:113. 路径总和 II

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树,以及目标和 sum = 22

  1. 5
  2. / \
  3. 4 8
  4. / / \
  5. 11 13 4
  6. / \ / \
  7. 7 2 5 1

返回:

  1. [
  2. [5,4,11,2],
  3. [5,8,4,5]
  4. ]

分析:使用深度优先遍历,用递归方法实现,所以递归的终止条件要写清楚,另外不要忘记状态的恢复。

Python 代码:

  1. class TreeNode(object):
  2. def __init__(self, x):
  3. self.val = x
  4. self.left = None
  5. self.right = None
  6. class Solution(object):
  7. def findPath(self, root, sum):
  8. """
  9. :type root: TreeNode
  10. :type sum: int
  11. :rtype: List[List[int]]
  12. """
  13. res = []
  14. if root is None:
  15. return res
  16. self.__dfs(root, sum, [], res)
  17. return res
  18. def __dfs(self, node, residue, path, res):
  19. # 递归,就应该先写递归终止条件
  20. if node is None:
  21. return
  22. # 走到这里 node 肯定非空,所以可以使用 left 和 right 成员变量
  23. # 走完以后,要记得回溯,状态要重置
  24. # 先把它加到路径中,在各种 if 都不成立的最后,要记得 pop 出去
  25. path.append(node.val)
  26. if node.left is None and node.right is None:
  27. # 如果是叶子结点,并且 residue 就等于当前结点的值
  28. if node.val == residue:
  29. res.append(path[:])
  30. # 注意:这里不要 return ,如果要 return,return 之前把 path 执行 pop 操作
  31. # 走到这里是非叶子结点,所以左边要走一走,右边也要走一走
  32. if node.left:
  33. self.__dfs(node.left, residue - node.val, path, res)
  34. if node.right:
  35. self.__dfs(node.right, residue - node.val, path, res)
  36. path.pop()

另一种等价的写法:

Python 代码:

  1. class Solution(object):
  2. def findPath(self, root, sum):
  3. """
  4. :type root: TreeNode
  5. :type sum: int
  6. :rtype: List[List[int]]
  7. """
  8. res = []
  9. if root is None:
  10. return res
  11. self.__dfs(root, sum, [], res)
  12. return res
  13. def __dfs(self, node, residue, path, res):
  14. if node is None:
  15. return
  16. path.append(node.val)
  17. residue -= node.val
  18. if node.left is None and node.right is None and residue == 0:
  19. # 才用结算
  20. res.append(path[:])
  21. path.pop()
  22. return
  23. if node.left:
  24. self.__dfs(node.left, residue, path, res)
  25. if node.right:
  26. self.__dfs(node.right, residue, path, res)
  27. path.pop()

(本节完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注