Leetcode 113: 경로 총 II (가장 자세한 해법!!!)

두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 다음과 같은 두 갈래 트리와 목표 및 sum = 22를 지정합니다.

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

반환:

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

문제 풀이 사고방식
이 문제는 아래의 두 문제와 매우 유사하다.
Leetcode 112: 경로 총화(가장 자세한 해법!!!)
Leetcode 257: 두 갈래 나무의 모든 경로(가장 자세한 해법!!!)
방문한 노드가 일 때, 우리는 list 를 새로 만들어서 result 에 삽입한 다음 result 로 돌아갑니다.각각 를 훑어보고 그들을 앞에 꽂으면 된다.

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        result = list()
        if root == None:
            return result

        if not root.left and not root.right and sum == root.val:
            result.append([root.val])
            return result

        left = self.pathSum(root.left, sum - root.val)
        for i in left:
            i.insert(0, root.val)
            result.append(i)

        right = self.pathSum(root.right, sum - root.val)
        for i in right:
            i.insert(0, root.val)
            result.append(i)

        return result

이 문제를 어떻게 교체해서 해결하는지 봅시다. 여기 저희와 이전 문제 Leetcode 257: 두 갈래 나무의 모든 경로(가장 상세한 해법!!!)
의 작법은 큰 차이가 없다. 단지 string 이 list 이 되고 변수sum의 차이가 많아졌다.

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """    
        result = list()
        if not root:
            return result

        stack = [(list(), sum, root)]
        while stack:
            path, val_, node = stack.pop()

            if node:
                path.append(node.val)
                if not node.left and not node.right and val_ == node.val:
                    result.append(path)

                stack += [(path.copy(), val_ - node.val, node.left), (path.copy(), val_ - node.val, node.right)]

        return result

여기에서 우리는 path.copy()에 주의해야 한다. 이것은 string 불변 유형이고 값을 통해 전달되기 때문이다. list 은 가변 유형이고 인용을 통해 전달되기 때문에 list 값을 통해 전달하려면 반드시 사용해야 한다copy.
이 문제의 첫 번째 귀속 실현cpp 버전은 약간의 함정이 있어 나의 실현을 참고할 수 있다.

class Solution 
{
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) 
    {
        vector<vector<int>> result;
        if (root == nullptr) return result;
        if (root->left == nullptr and root->right == nullptr and sum == root->val) 
        {
            result.push_back(vector<int>(1, root->val));// 1
            return result;
        }
        vector<vector<int>> left = pathSum(root->left, sum - root->val);
        for (auto& i : left)
        {
            i.insert(i.begin(), 1, root->val);// 2
            result.push_back(i);
        }
        vector<vector<int>> right = pathSum(root->right, sum - root->val);
        for (auto& i : right)
        {
            i.insert(i.begin(), 1, root->val);
            result.push_back(i);
        }
        return result;
    }
};

그래서 귀속하면 아래 의 방식으로 쓰는 것을 추천합니다.

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """   
        result = list()     
        if not root:
            return result
        
        self._pathSum(result, list(), root, sum)       
        return result
    
    def _pathSum(self,result, path, node, num):
        if node:
            path.append(node.val)
            
            if not node.left and not node.right and num == node.val:
                result.append(path.copy())
            
            self._pathSum(result, path, node.left, num - node.val)
            self._pathSum(result, path, node.right, num - node.val)
            path.pop()

이 질문의 다른 언어 버전을 GitHub Leetcode에 추가했습니다.
문제가 있으면 여러분이 지적해 주시기 바랍니다!!!