回溯
解题思路
根据 二叉树的先序遍历 和 回溯 可解决此题；
按照 根、左、右 的顺序，遍历树的所有节点；
在先序遍历中，记录从根节点到当前节点的路径；当路径满足根节点 左右子树到叶节点形成的路径 且 各节点值的和等于目标值 targetSum 时，将此路径加入结果列表；
图解
复杂度
-
时间复杂度：
O(N)，N 为二叉树的节点数，先序遍历需要遍历所有节点； -
空间复杂度：
O(N)，最差情况下，即树退化为链表时，path 存储所有树节点，使用O(N)额外空间；
代码实现
var pathSum = function (root, targetSum) {
let res = [];
backtrack(res, root, targetSum, []);
return res;
};
const backtrack = (res, root, target, path) => {
if (root === null) return;
path.push(root.val);
target -= root.val;
// 递归结束条件 => 叶子节点 && 路径和等于 target
if (target === 0 && root.left === null && root.right === null) {
res.push([...path]);
}
// dfs 左孩子和 dfs 右孩子只是表示的每一种分支的选择，当到达叶子结点只需要 pop 一次
backtrack(res, root.left, target, path);
backtrack(res, root.right, target, path);
path.pop();
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 112. 路径总和
上一篇
评论
