LeetCode 112 路径总和（path-sum）

1.题目

• 难度：简单

• 涉及知识：树、广度优先搜索

• 题目：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
  

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

• 示例：

给定如下二叉树，以及目标和 sum = 22，

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

• 题目地址：leetcode-cn.com/problems/pa…

2.解题：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if(!root){
        return false;
    }
    sum = sum - root.val;
    if(!root.left && !root.right){
        return sum === 0;
    }
    //如果还有子节点，则继续递归遍历该节点的孩子
    return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
};

• LeetCode Submit

执行用时 :92 ms, 在所有 JavaScript 提交中击败了89.42%的用户
内存消耗 :37.1 MB, 在所有 JavaScript 提交中击败了51.15%的用户

3.解析

• 递归方式
  

同前面二叉树遍历方式，总体采用递归方式进行。

• 正向思路 和 反向思路
  

kk一开始的思路是采用正面的思路，即输入固定的sum值22，遍历每条路径取得总和，与sum进行比对，后来发现这样的做法性能并不高
改用反向思路，即从sum开始处理，每遍历一项，就从sum当中减去相应的该节点的值，如果减到最后（没有left，right节点）的情况，sum若为0即视为该二叉树存在该路径总和。

有方法优化请各位多多指教！