剑指Offer题解 - Day32

「剑指 Offer 34. 二叉树中和为某一值的路径」

力扣题目链接[1]

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

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

示例 1：

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

示例 2：

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

「提示：」

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

思路：

根据题目要求，要寻找根节点到叶子节点匹配的路径，也就是说我们需要遍历二叉树。这里采取先序遍历，同时记录匹配的路径的方式。

所谓先序遍历，就是先获取根节点的值，然后递归获取左子节点，然后递归获取右子节点。

先来看最终的代码，然后具体分析：

先序遍历

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

const pathSum = (root, target) => {
    let result = []; // 初始化结果数组
    let path = []; // 初始化放置路径的数组
    const recur = (root, target) => { // 递归函数
        if (!root) return; // 递归终止条件
        path.push(root.val) // 先序获取根节点的值，并放至路径数组中
        target -= root.val; // 递减目标值，方便传入子节点递归
        if (target === 0 && !root.left && !root.right) {
            result.push([...path]); // 满足条件便放至结果数组
        }
        recur(root.left, target) // 递归左子节点
        recur(root.right, target) // 递归右子节点
        path.pop() // 回溯时弹出放入的值
    }
    recur(root, target) // 开始递归
    return result; // 返回最终结果
};

• 「时间复杂度 O(n)」。
• 「空间复杂度 O(n)」。

分析：

既然是递归的进行先序遍历，那么重点就在于递归函数里的逻辑。在主函数中，我们声明了结果数组和存放路径的数组，调用递归函数并返回结果值。

进入到递归函数，首先不能忘记递归终止条件。当我们递归到叶子节点的子节点的时候，就需要直接返回。

然后将当前节点的值放入路径数组中，同时将传入的第二个参数进行递减。因为函数的传参是按值传递，所以不用担心会对调用栈其他函数造成影响。

此时需要判断是否符合条件，需要满足两个条件：

1. 当前节点时叶子节点
2. 当前的目标值已被递减为 0，说明路径数组中的值相加刚好等于主函数中的目标值

当满足条件时，就将路径数组进行浅拷贝，放至结果数组中。不能直接放至是因为数组是引用类型，必须拷贝一份副本才不会造成影响。

其实如果满足条件的话，意味着当前节点就是叶子节点，而叶子节点不存在子节点，在if判断里可以提前返回。如果不提前返回也可以，因为再次递归子节点会符合第一行代码，也会进行返回。

因此，不管当前节点是否有子节点，我们都可以进行递归左右子节点。

最后，回溯的时候需要将path中被添加的值弹出。因为我们只维护了一个路径数组，不弹出的话，会对其他分支造成影响。

总结

本题通过先序遍历进行题解。而先序、中序、后序遍历的区别也要掌握。本题需要注意的点就是路径数组，放至结果数组中需要浅拷贝，回溯的时候需要弹出遍历时添加的值。

复杂度方面，由于需要遍历二叉树所有的节点，因此时间复杂度是O(n) 。最坏情况下，当二叉树退化为链表时，需要存储二叉树所有的节点，因此空间复杂度是O(n) 。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dy6pt/