112. 路径总和

;(function () {
  /**
   * 112. 路径总和
   * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
   * 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
   * 如果存在，返回 true ；否则，返回 false 。
   * 叶子节点 是指没有子节点的节点。
   *
   * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
   * 输出：true
   *
   * 输入：root = [1,2,3], targetSum = 5
   * 输出：false
   * 树中存在两条根节点到叶子节点的路径：
   * (1 --> 2): 和为 3
   * (1 --> 3): 和为 4
   * 不存在 sum = 5 的根节点到叶子节点的路径。
   *
   * 输入：root = [], targetSum = 0
   * 输出：false
   *
   */
  class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
      this.val = val === undefined ? 0 : val
      this.left = left === undefined ? null : left
      this.right = right === undefined ? null : right
    }
  }

  function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    // 方法一：
    let res: number[] = []
    if (!root) {
      return false
    }
    function preorder(root: TreeNode | null, total: number) {
      if (!root) {
        // console.log(total)
        return
      }
      total += root.val
      preorder(root.left, total)
      preorder(root.right, total)
      // 没有子节点的节点
      if (!root.left && !root.right) {
        res.push(total)
      }
    }
    preorder(root, 0)
    return res.includes(targetSum)

    // 方法二：

    // 方法三：
  }
})()