路径总和

二 题目

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * 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) {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三 解题思路

上手直接套路：

递归

/**
 * 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}
 */
const hasPathSum = (root, sum) => {
  if (!root) {
    return false;
  }
  let result = false;

  const ergodic = (root, ergSum = 0) => {
    if (!root) {
      return;
    }
    ergSum += root.val;
    if (ergSum === sum && !root.left && !root.right) {
      result = true;
    }
    ergodic(root.left, ergSum);
    ergodic(root.right, ergSum);
  };
  ergodic(root, 0);

  return result;
};

const root = {
  val: 5,
  left: {
    val: 4,
    left: {
      val: 11,
      left: { val: 7, left: null, right: null },
      right: { val: 2, left: null, right: null },
    },
    right: null,
  },
  right: {
    val: 8,
    left: { val: 13, left: null, right: null },
    right: {
      val: 4,
      left: null,
      right: { val: 1, left: null, right: null },
    },
  },
};
console.log(hasPathSum(root, 22));

它的核心在于：

const ergodic = (root) => {
  if (!root) {
    return;
  }
  ergodic(root.left);
  ergodic(root.right);
};

这份代码可以直接遍历树，牢记一下即可。

然后参考下官方题解，是可以简化一下的：

递归 - 官方题解版

const hasPathSum = (root, sum) => {
  if (!root) {
    return false;
  }
  if (!root.left && !root.right) {
    return sum === root.val;
  }
  return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
};

为啥子写不出像官方这样精简的代码，大概就是菜，然后懒得想。

套路一上直接搞定，谁还会进一步优化自己代码？

最后上演树的第二种套路：迭代

迭代

const hasPathSum = (root, sum) => {
  if (!root) {
    return false;
  }
  const queNode = [root];
  const queValue = [root.val];
  while (queNode.length) {
    const now = queNode.pop();
    const temp = queValue.pop();
    if (!now.left && !now.right) {
      if (temp === sum) {
        return true;
      }
      continue;
    }
    if (now.left) {
      queNode.push(now.left);
      queValue.push(now.left.val + temp);
    }
    if (now.right) {
      queNode.push(now.right);
      queValue.push(now.right.val + temp);
    }
  }
  return false;
};

迭代树的代码简化如下：

const nowRoot = [root];
while (node.length) {
  const tempRoot = nowRoot.pop();
  if (tempRoot.left && tempRoot.left.val) {
    nowRoot.push(tempRoot.left);
  }
  if (tempRoot.right && tempRoot.right.val) {
    nowRoot.push(tempRoot.right);
  }
}

这道题中，我们需要使用第二条路，用来记录当前的值，于是就有上面的代码。

不懂？那就 debug 或者 console 看看吧，没那么复杂~

四 统计分析

本题不需要统计分析。

五 套路分析

本题套路：

1. 递归
2. 迭代

代码如下：

递归

const ergodic = (root) => {
  if (!root) {
    return;
  }
  ergodic(root.left);
  ergodic(root.right);
};

迭代

const nowRoot = [root];
while (node.length) {
  const tempRoot = nowRoot.pop();
  if (tempRoot.left && tempRoot.left.val) {
    nowRoot.push(tempRoot.left);
  }
  if (tempRoot.right && tempRoot.right.val) {
    nowRoot.push(tempRoot.right);
  }
}

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。