输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
/*** 二叉树结点类*/class Node {constructor(value = 0, left = null, right = null) {this.value = value;this.left = left;this.right = right;}}/**** @param {Node} root* @param {Number} target*/function findPath(root, target) {const paths = []; // 存放所有满足条件的路径let sum = 0; // 路径上的节点值的总和function _findPath(node, path) {if (node === null) {return;}// 把当前节点放入路径中sum = sum + node.value;path.push(node);const isLeaf = node.left === null && node.right === null;// 如果是叶节点, 并且路径上的节点和满足条件, 记录这条路径if (isLeaf && sum === target) {paths.push([...path]);}// 当前节点有左子树, 向左子树递归if (node.left !== null) {_findPath(node.left, path);}// 当前节点有右子树, 向右子树递归if (node.right !== null) {_findPath(node.right, path);}// 把当前节点从路径中移除sum = sum - node.value;path.pop(node);}_findPath(root, []);return paths;}/*** 以下是测试代码*/const root = new Node(1, new Node(2), new Node(3, null, new Node(-1)));console.log(findPath(root, 3));