1. // 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
    3. // 叶子节点 是指没有子节点的节点。
    5. //  
    7. // 示例 1：
    10. // 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
    11. // 输出：true
    12. // 解释：等于目标和的根节点到叶节点路径如上图所示。
    13. // 示例 2：
    16. // 输入：root = [1,2,3], targetSum = 5
    17. // 输出：false
    18. // 解释：树中存在两条根节点到叶子节点的路径：
    19. // (1 --> 2): 和为 3
    20. // (1 --> 3): 和为 4
    21. // 不存在 sum = 5 的根节点到叶子节点的路径。
    22. // 示例 3：
    24. // 输入：root = [], targetSum = 0
    25. // 输出：false
    26. // 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
    28. /**
    29.  * Definition for a binary tree node.
    30.  * function TreeNode(val, left, right) {
    31.  *     this.val = (val===undefined ? 0 : val)
    32.  *     this.left = (left===undefined ? null : left)
    33.  *     this.right = (right===undefined ? null : right)
    34.  * }
    35.  */
    36. /**
    37.  * @param {TreeNode} root
    38.  * @param {number} targetSum
    39.  * @return {boolean}
    40.  */
    41. // 题解，深度优先遍历求和，最大深度记录层级类似
    42. var hasPathSum = function (root, targetSum) {
    43.     if (!root) { return false }
    45.     let res = false;
    46.     const dfs = (n, s) => {
    47.         // 判断叶子节点
    48.         if (n.left === null && n.right === null && s === targetSum) {
    49.             res = true
    50.         }
    52.         if (n.left) { dfs(n.left, n.left.val + s) };
    53.         if (n.right) { dfs(n.right, n.right.val + s) }
    55.     }
    57.     dfs(root, root.val)
    59.     return res
    60. };

    时间复杂度：O（n） 最差空间复杂度O(N) 均匀分布O（log N）