题目描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

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

提示：

• 树中节点总数在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

测试用例

用例1：

• 输入：root = [5,4,8,11,null,13,4,7,2,null,null，null,null,5,1], targetSum = 22
• 输出：[[5,4,11,2],[5,8,4,5]]

用例2

• 输入：root = [1,2,3], targetSum = 5
• 输出：[]

思路

深度遍历树，如果有符合条件的结果就放入res，如果遍历到根节点不符合条件就回溯到上一个节点，继续遍历，直到遍历完整颗树，结束

代码实现

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[][]}
 */

var res = [];
var path = [];
var pathSum = function (root, target) {
  if (!root) {
    return [];
  }
  dfsFind(root, 0, target);
  return res;
};

function dfsFind(root, sum, target) {
  if (!root) {
    return;
  }
  path.push(root.val);
  sum += root.val;
  // 到根节点了 同时和也等于target了

  if (sum === target && root.left === null && root.right == null) {
    res.push([...path]);
    // return;
  }
  if (root.left) {
    dfsFind(root.left, sum, target);
  }
  if (root.right) {
    dfsFind(root.right, sum, target);
  }
  // 回溯
  path.pop();
}

pathSum(arr[0], target);
console.log("结果为: ", res);

/* 
  请输入二叉树数组
  5,4,8,11,null,13,4,7,2,null,null,null,null,5,1
  请输入target:
  22
  结果为:  [ [ 5, 4, 11, 2 ], [ 5, 8, 4, 5 ]]
*/