首页 > ACM题库 > LeetCode > Path Sum II-LeetCode
2014
09-02

Path Sum II-LeetCode

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22

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

return

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

题目链接:https://oj.leetcode.com/problems/path-sum-ii/

题目比上一题 Path Sum 多了一个打印路径的要求。需要使用回溯法,记录当前的路径。在到达叶子节点时,判断是否符合要求,符合的话就复制当前路径到结果中。

Java代码如下:

public class Solution {
     public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> lists = new ArrayList();
        List<Integer> list = new ArrayList<Integer>();
        pathSumRecur(root,sum,lists,list);
        return lists;
    }

    public void pathSumRecur(TreeNode root, int sum,List<List<Integer>> lists, List<Integer> list) {
        if(root == null) return;
        list.add(root.val);
        if(root.left == null && root.right == null && root.val == sum){
        	List<Integer> newList = new ArrayList<Integer>(list);//拷贝至新的链表
        	lists.add(newList);
        }
        pathSumRecur(root.left,sum-root.val,lists,list);
        pathSumRecur(root.right,sum-root.val,lists,list);

        list.remove(list.size()-1);//回溯
    }
}

  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”