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]

]

 
제목 대의: 두 갈래 나무와 한 개의 수를 주고 뿌리 노드에서 잎 결점까지의 합이 이 수와 같은 모든 경로를 구한다.
문제 풀이 사고방식: DFS, 먼저 현재 노드를 창고에 넣은 다음에 각각 좌우 서브트리로 귀속합니다. 만약에 현재 노드가 비어 있으면 바로 종료합니다. 만약에 현재 노드가 잎결점이지만 루트 노드까지의 경로와 지정한 수와 같지 않으면 바로 종료합니다. 만약에 지정한 수와 같으면 이 경로를 결과 목록에 추가하고 귀속이 끝난 후에 이전 층으로 되돌아갑니다.

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

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

        if (root == null) {

            return res;

        }

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

        path(root, tmp, res, sum);

        return res;

    }



    public void path(TreeNode node, List<Integer> tmp, List<List<Integer>> res, int sum) {

        if (node == null) {

            return;

        }

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

            return;

        }

        tmp.add(node.val);

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

            res.add(new ArrayList<>(tmp));

            tmp.remove(tmp.size() - 1);

            return;

        }

        path(node.left, tmp, res, sum - node.val);

        path(node.right, tmp, res, sum - node.val);

        tmp.remove(tmp.size() - 1);

    }