Java实现 LeetCode 113 路径总和 II

113. 路径总和 II

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

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

示例:

给定如下二叉树，以及目标和 sum = 22，

          5

         / \

        4   8

       /   / \

      11  13  4

     /  \    / \

    7    2  5   1

[

[5,4,11,2],

[5,8,4,5]

]



class Solution {

   public List<List<Integer>> pathSum(TreeNode root, int sum) {

        if(root == null) return new ArrayList<>();

        List<List<Integer>> ans = new ArrayList<>();

        if(root.val == sum && root.left == null && root.right == null){

            List<Integer> arr = new ArrayList<>();

            arr.add(root.val);

            ans.add(arr);

            return ans;

        }

        List<List<Integer>> left = pathSum(root.left,sum - root.val);

        List<List<Integer>> right = pathSum(root.right,sum - root.val);

        for(List<Integer> list : left){

            //这里的插入到指定坐标会让后面的自动向后排序

           list.add(0,root.val);

           ans.add(list);

        }

        for(List<Integer> list : right){

           list.add(0,root.val);

           ans.add(list);

        }

        return ans;

    }

}

巴特西

Java实现 LeetCode 113 路径总和 II

113. 路径总和 II

最新文章

热门文章