112. 路径总和

题目

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

# 给定如下二叉树，以及目标和 sum = 22，
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

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

思路

• sum —— 从根节点到叶子节点的路径上的节点值相加的目标和
• 递归。转为判断：左、右子树中能否找出和为 sum - root.val 的路径
• 每遍历一个节点，sum 就减去当前节点值，当遍历到叶子节点时，已经没有子节点了，如果 sum - 当前叶子节点值 == 0 ，就是找到了从根节点到叶子节点的和为 sum 的路径 时间复杂度：O(n)，每个节点被遍历一次

作者：xiao_ben_zhu 链接：https://leetcode-cn.com/problems/path-sum/solution/di-gui-ti-by-hyj8/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

dfs(递归)

const hasPathSum = (root, sum) => {
  if (root == null) return false;                // 遍历到null节点
  if (root.left == null && root.right == null) { // 遍历到叶子节点
    return sum - root.val == 0;                  // 如果满足这个就返回true
  }
  return hasPathSum(root.left, sum - root.val) ||
    hasPathSum(root.right, sum - root.val);      // 大问题转成两个子树的问题
}

bfs(迭代)

/**
 * 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 === null) return false;
  let stack = [root];
  let sumStack = [sum - root.val];
  while (stack.length > 0) {
    let node = stack.pop();
    let curSum = sumStack.pop();
    if (node.left === null && node.right === null && curSum === 0) {
      return true;
    }
    if (node.right !== null) {
      stack.push(node.right);
      sumStack.push(curSum - node.right.val);
    }
    if (node.left !== null) {
      stack.push(node.left);
      sumStack.push(curSum - node.left.val);
    }
  }
  return false;
};

作者：GuYueJiaJie
链接：https://leetcode-cn.com/problems/path-sum/solution/javascript-di-gui-die-dai-by-guyuejiajie/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。