leetcode算法【113】路径总和 II

青旅半醒 2022-11-26 07:39 130阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
    
    说明: 叶子节点是指没有子节点的节点。
    
    示例:
    给定如下二叉树，以及目标和 sum = 22，
    
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1
    返回:
    
    [
       [5,4,11,2],
       [5,8,4,5]
    ]

#### 方案： ####

/** * 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) { 
                if (root == null) return new LinkedList<>( );
                else if (root.left == null && root.right == null) { 
                    if (root.val - sum == 0) { 
                        List<List<Integer>> res = new LinkedList<>( );
                        LinkedList<Integer> tmp = new LinkedList<>( );
                        tmp.add(root.val);
                        res.add(tmp);
                        return res;
                    }
                } else { 
    // pathSum(root.left, sum - root.val) || pathSum(root.right, sum - root.val)
                    List<List<Integer>> res = new LinkedList<>( );
                    LinkedList<LinkedList<Integer>> tmp = (LinkedList)pathSum(root.left, sum - root.val);
                    tmp.addAll((LinkedList)pathSum(root.right, sum - root.val));
                    for (int i = 0; i < tmp.size( ); i++) { 
                        tmp.get(i).addFirst(root.val);
                        res.add(new LinkedList<>(tmp.get(i)));
                    }
                    return res;
                }
                return new LinkedList<>( );
            }
        }

##### 复杂度计算 #####

*  说实话，有点浪费
 *  时间复杂度：O(n)
 *  空间复杂度：O(n^2)

[Git]: https://github.com/ch98road/leetcode