V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  程序员

[Leetcode] 113. 路径总和 II

  •  
  •   Acceml ·
    Acceml · 2019-04-14 10:23:38 +08:00 · 1693 次点击
    这是一个创建于 964 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

    说明: 叶子节点是指没有子节点的节点。

    示例: 给定如下二叉树,以及目标和 sum = 22,

                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1
    

    返回:

    [
       [5,4,11,2],
       [5,8,4,5]
    ]
    

    题解

    这道题目是上一道的延伸,但是需要记录下路径,返回回去。这就是一个典型的 backtrack 的题目了。我们用迭代的方式需要记录中间的路径状态,稍显复杂,所以我们想用递归的方式来解,先探索左子树,然后探索右子树。如果都探索完之后,右满足的就加入到最终结果中。

    public class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> res = new LinkedList<>();
            helper(root, sum, res, new LinkedList<>());
            return res;
        }
    
        public void helper(TreeNode root, int sum, List<List<Integer>> res, List<Integer> current) {
            if (root == null) {
                return;
            }
            current.add(root.val);
            if (root.left == null && root.right == null && sum == root.val) {
                // leaf node.
                res.add(new LinkedList<>(current));
                // back track.
                current.remove(current.size() - 1);
                return;
            }
    
            helper(root.left, sum - root.val, res, current);
            helper(root.right, sum - root.val, res, current);
            // back track.
            current.remove(current.size() - 1);
        }
    }
    

    热门阅读

    Leetcode 名企之路 手撕代码 QQ 群:805423079, 群密码:1024

    9 条回复    2019-04-16 12:31:47 +08:00
    shiww
        1
    shiww  
       2019-04-14 16:20:45 +08:00 via iPhone
    感觉还可以提前排除已经大于 sum 的情况
    usingnamespace
        2
    usingnamespace  
       2019-04-15 01:26:53 +08:00 via iPhone
    这题我如果面试出出来估计更想看到自底向上 dp
    usingnamespace
        3
    usingnamespace  
       2019-04-15 01:27:56 +08:00 via iPhone
    建议不是很好的方法的解法就不要发了
    geelaw
        4
    geelaw  
       2019-04-15 01:38:42 +08:00
    @usingnamespace #2 实际上你想象中的做法并不能改进复杂度。那么你要不要“不是很好的方法的解法就不要发了”?
    usingnamespace
        5
    usingnamespace  
       2019-04-15 11:19:36 +08:00 via iPhone
    @geelaw ?麻烦分析下复杂度 这个递归有多少分支? 最后是 O(nlogn) 还不说递归本身的栈空间消耗 dp 自底向上一趟完成 O(n)
    如果你觉得区别不大那就不用说了
    usingnamespace
        6
    usingnamespace  
       2019-04-15 11:21:29 +08:00 via iPhone
    @geelaw 我想象中的? dp 小白题可能对于你来说是只能想象的😁
    usingnamespace
        7
    usingnamespace  
       2019-04-15 11:22:04 +08:00 via iPhone
    @geelaw 也许是你想不到怎么 o(n)复杂度吧
    geelaw
        8
    geelaw  
       2019-04-15 22:55:08 +08:00
    @usingnamespace #5 #6 #7 你可以再想一想,给你个提示:这个问题的答案的长度可以是 Omega(n log n)。以及这个问题里面并没有重叠子问题,你想象中的解法只不过是把递归手工展开。
    usingnamespace
        9
    usingnamespace  
       2019-04-16 12:31:47 +08:00 via iPhone
    @geelaw 是没有 但是仍然是 nlogn
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1032 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 20ms · UTC 22:48 · PVG 06:48 · LAX 14:48 · JFK 17:48
    ♥ Do have faith in what you're doing.