题目描述:输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的 list 中,数组长度大的数组靠前)
这题和LeetCode.113. 路径总和 II一样。
输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的 list 中,数组长度大的数组靠前)
这题和LeetCode.113. 路径总和 II一样。
算法实现思路是:
上面整个过程就是一个前序遍历,但在遍历的过程中,动态地维护了当前路径与总和的信息。
在实现过程中需要注意的是,JavaScript 中传入数组做参数,函数内拿到的是数组的引用,不是深拷贝。代码实现如下:
// ac地址:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
// 原文地址:https://xxoo521.com/2020-02-04-btree-find-path/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {number[][]}
*/
var pathSum = function(root, sum) {
if (!root) {
return [];
}
const pathes = [];
__pathSum(root, sum, pathes, []);
return pathes;
};
function __pathSum(root, sum, pathes, path) {
if (!root) {
return;
}
path = [...path, root.val]; // 深拷贝
if (!root.left && !root.right && root.val === sum) {
pathes.push(path);
return;
}
__pathSum(root.left, sum - root.val, pathes, path);
__pathSum(root.right, sum - root.val, pathes, path);
}
这里可以借助栈,改造成非递归前序遍历。从而减少运行时间。
为了方便表示节点信息,栈中的元素是形如(node, 剩余路径和, 节点路径组成的数组)
这样的元祖。
整体的处理流程是:
注意,为什么先处理右节点而不是左节点?先遍历左和右都可以。但是因为用的牛客网的 oj 平台,这里要求“数组长度大的数组靠前”,先遍历左节点就是 oc 不了。
代码实现如下:
// ac地址:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
// 原文地址:https://xxoo521.com/2020-02-04-btree-find-path/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {number[][]}
*/
var pathSum = function(root, sum) {
if (!root) {
return [];
}
const statck = [[root, sum, [root.val]]];
const result = [];
while (statck.length) {
const [node, num, path] = statck.pop();
if (!node.left && !node.right && node.val === num) {
result.push(path);
}
if (node.right) {
statck.push([
node.right,
num - node.val,
[...path, node.right.val]
]);
}
if (node.left) {
statck.push([node.left, num - node.val, [...path, node.left.val]]);
}
}
return result;
};
如果题目说明了:所有节点的值都是正数,那么在递归遍历的时候,就可以进行回溯剪枝。
剪枝的方法就是如果发现当前的节点的值大于 sum,停止递归。
改动后的__pathSum()
的代码如下:
// 原文地址:https://xxoo521.com/2020-02-04-btree-find-path/
function __pathSum(root, sum, pathes, path) {
if (!root || root.val > sum) {
// 剪枝
return;
}
path = [...path, root.val];
if (!root.left && !root.right && root.val === sum) {
pathes.push(path);
return;
}
__pathSum(root.left, sum - root.val, pathes, path);
__pathSum(root.right, sum - root.val, pathes, path);
}
有意思的是这段代码在牛客网平台可以直接 oc 本题,测试用例不全面。