题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

测试用例

用例1

• 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
• 输出：true
• 解释：等于目标和的根节点到叶节点路径如上图所示。

用例2

• 输入：root = [1,2,3], targetSum = 5
• 输出：false
• 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。

思路

回溯实现 —— 参考代码中的注释

代码实现

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入二叉树数组");
const a = readline()
  .split(",")
  .map((item) => {
    if (item == "null") {
      return null;
    } else {
      return Number(item);
    }
  });

let arr = [];
// 二叉树数组内的值转为TreeNode
for (let i = 0; i < a.length; i++) {
  arr[i] = new TreeNode(a[i]);
}

// 构造二叉树
for (let i = 0; i <= arr.length / 2 + 1; i++) {
  if (arr[2 * i + 1]) {
    if (arr[2 * i + 1].val != null) {
      arr[i].left = arr[2 * i + 1];
    }
  }
  if (arr[2 * i + 2]) {
    if (arr[2 * i + 2].val != null) {
      arr[i].right = arr[2 * i + 2];
    }
  }
}

console.log("请输入target: ");
const target = Number(readline());

/*
 * @param {TreeNode} root
 * @param {number} target
 * @return {number[][]}
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */

var hasPathSum = function (root, targetSum) {
  if (!root) {
    return false;
  }
  return traversal(root, root.val, targetSum);
};

function traversal(root, sum, targetSum) {
  // sum += root.val;
  // 到根节点了
  if (root.left == null && root.right == null) {
    if (targetSum === sum) {
      return true;
    }
    return false;
  }
  if (root.left) {
    sum += root.left.val; // 把左子树的值加入sum
    // 遍历左子树，如果找到了符合条件的，就返回true
    if (traversal(root.left, sum, targetSum)) {
      return true;
    }
    sum -= root.left.val; // 回溯
  }
  if (root.right) {
    sum += root.right.val; // // 把左子树的值加入sum
    // 遍历右子树，如果找到了符合条件的，就返回true
    if (traversal(root.right, sum, targetSum)) {
      return true;
    }
    sum -= root.right.val; // 回溯
  }
  return false;
}

const ans = hasPathSum(arr[0], target);
console.log("结果为: ", ans);
/* 
  请输入二叉树数组
  5,4,8,11,null,13,4,7,2,null,null,null,1
  请输入target:
  22
  结果为:  true

  请输入二叉树数组
  1,2,3
  请输入target:
  5
  结果为:  false
*/