LeetCode 113. Path Sum II

二叉树的路径和 II – 找出满足二叉树的路径和的所有路径。

输入空间：二叉
解空间：二叉

解题“七步走” (保持这种sense)：

1. 题意 Scenario
2. 假设 Assumptions
3. 举例与输入输出 Examples and figure out Input/Output
4. 思路（什么数据结构， 什么算法）Thinking Process (What data structure, algorithm?)
5. 代码 Coding
6. 复杂度分析 Complexity Analysis
7. 测试 Tests

题目要求

原题链接
在给定的一个二叉树中，从全局的根节点开始，找出所有的到叶子的路径，使得路径上的各个节点加起来的和等于给定的数值。返回这些符合要求的路径，但假若一条符合的路径都没有，返回null。

举例与输入输出

例子直接用LeetCode上的图，还是很好理解的。

在本例子中，有两条路径是满足的，我们就要把这两条路径都包括在返回的对象当中进行返回。

思路: 本题主要讲如何利用已做题为模板，加以改造从而得出新题的答案

想想，我们上一期讲的是LeetCode 112. Path Sum，问的是是否存在一个路径上的各个点加起来等于目标值的路径。

那么，本期这个题目，我们就在存不存在的基础上，设置好要存储最终结果的数据结构，并进行微调去存储每一个可行的路径，就可以了。

LeetCode 112. Path Sum的答案代码如下：

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        // Base case 1: 已经走到叶子节点之下的null节点，发现叶子节点的值无法等于当前目标值
        if (root == null) {
            return false;
        }

        // Base case 2: 在叶子节点时叶子节点的值能等于当前目标值
        else if (root.left == null && root.right == null && root.val == sum) {
            return true;
        }

        boolean left = hasPathSum(root.left, sum - root.val);
        boolean right = hasPathSum(root.right, sum - root.val);

        return left || right;
    }
}

显然，LeetCode 112的Base Cases的情况，即判断一条路径是否符合要求，是可以复用的代码片段。
另外就是，它的分治法中的“分”的过程，也可以为LeetCode 113所用，只是LC 113需要在分的过程中带上更多的参数。

为什么LC 113会要带上更多参数呢？
是因为，就本题LeetCode 113而言，我们要存储的最终结果是所有符合的路径。那么在这个最终结果能得到之前，我们要存储单个的符合路径，Java中，我们可以用List<Integer>，而后，所有的符合的路径就是List of List，即存最终结果的表面型就是List<List<Integer>>。之所以选择List这个数据结构，在于它从后面插入数据、删除数据，都很方便。把数据插入到List最后的时间复杂度为O(1)，删除List的最后一个元素的时间复杂度也为O(1)，很高效。

那为什么又要用到List的删除操作呢？
这是因为在前序遍历选取一条路径的时候，我们不能保证选到的一定是对的，当发现不对的时候，我们就有必要弹出已经进入到可能的正确路径List中的数值，把机会留给下一个可能的节点上的数。就拿👆的截图来举例，一开始，我们走的是最左边的5->4->11->7这个路线，当我们走到7这个叶子节点的时候，发现此时的sum为2（读者想一想此时为什么sum值为2，答案可以参看上一期推文），与7是不相等的，所以，我们就有必要把已经压入List的7这个数字给扔掉，让位给下一个叶子。下一个遍历到的叶子刚好为2，那么我们把2予以保留，并把整个正确路径的List存到大的二维的List of List之中。

其实，上面这段说的就是“回溯”（Backtracking）的思想。好，说了这么多，给大家看本题的代码吧，或许大家会更好理解一点。我在大家看完代码之后会再针对代码给出一些讲解。

本题代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 class Solution {
   public List<List<Integer>> pathSum(TreeNode root, int sum) {
       List<List<Integer>> res = new ArrayList<>();
       List<Integer> tmp = new ArrayList<>();
       dfsSum(root, sum, tmp, res);
       return res;
   }
   public void dfsSum(TreeNode root, int sum, List<Integer> tmp, List<List<Integer>> res) {
       if (root == null) {
          return;
       }
       tmp.add(root.val);
       if (root.left == null && root.right == null && root.val == sum) {
          res.add(new ArrayList(tmp));
       }

       dfsSum(root.left, sum - root.val, tmp, res);
       dfsSum(root.right, sum - root.val, tmp, res);
       tmp.remove(tmp.size() - 1);
   }
}

代码讲解

1. 主函数pathSum()设置好了存最终答案的变量res，以及存每一条符合要求的路径的变量tmp。注意这两个变量的表面型(apparent type)与实际型(actual type)。表面型与实际型这是Java语法的知识点，这里就不予以展开了。
2. 辅助函数dfsSum()，之所以叫dfs是因为它是depth first search（深度优先搜索）的缩写。二叉树的纵向的递归遍历，不论是前序、中序还是后序，都是二叉树的深度优先搜索模式。笔记哥以后会给大家看二叉树的BFS（breadth first search 广度优先搜索）的题目。
3. 这个辅助函数也是跟LC 112答案代码类似的地方，大家可以着重看一下，辅助函数带了几个参数，为什么要带这些参数。
4. 在辅助函数内部，我们可以看到那两个在LC 112答案代码出现的base cases. 注意，两个base cases之间出现的那个tmp.add(root.val);，这是因为当我们遍历到一个节点时，我们都暂且无法判断该节点是否能成为正确路径上的节点，所以就都先要存起来。那什么时候把非正确路径的节点“吐”出来呢？就是在分治法之后的“治”的那一步tmp.remove(tmp.size() - 1);，可以看出吐出来的是List的最后一个元素。
5. 当形成正确路径的情况下，我们把tmp所存的路径加到最后的结果中，用的是res.add(new ArrayList(tmp));。再次的，由于Java语言的表面型和实际型的区别，最终答案是List<List<Integer>>这个表面型，但往这个数据结构里面加元素，要求被加入的元素必须是一个实际型的，所以要把tmp进行ArrayList化，然后再加入。ArrayList化的方法也很简单，就是new ArrayList(某种Collection Type)就可以了。

时间空间复杂度

时间复杂度：遍历整个树的节点，所以是O(n)。
空间复杂度：为递归栈的深度，所以是O(log(n))。

• ← Previous Post
• Next Post →