LeetCode-112.路径总和

发表于 分类于

题目描述

给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回true；否则，返回false。

叶子节点 是指没有子节点的节点。

示例1

1
2
3
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例2

1
2
3
4
5
6
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例3

1
2
3
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示

  • 树中节点的数目在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

题解

  1. 递归法

    将路径之和问题拆解为左子树或右子树是否有和为目标值与当前节点值之差的路径

    1
    2
    3
    4
    5
    6
    7
    8
    9
    func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
      guard let root = root else {
        return false
      }
      if root.left === nil && root.right === nil {
        return root.val == targetSum
      }
      return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
    }

  2. 遍历法

    将路径之和问题拆解为到达当前节点时路径上的和与左子树或右子树的和相加等于目标值的问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    func hasPathSum2(_ root: TreeNode?, _ targetSum: Int) -> Bool {
      guard let root = root else {
        return false
      }
      var nodeStack = [root]
      var valStack = [root.val]
      while !nodeStack.isEmpty {
        let cur = nodeStack.popLast()! // 当前节点
        let curSum = valStack.popLast()! // 到当前节点时路径上的和
        if cur.left === nil && cur.right === nil && curSum == targetSum {
          return true
        }
        if let left = cur.left {
          nodeStack.append(left)
          valStack.append(curSum + left.val)
        }
        if let right = cur.right {
          nodeStack.append(right)
          valStack.append(curSum + right.val)
        }
      }
      return false
    }