[LeetCode] 경로 및 Path Sum

1878 단어 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
4
[
   [5,4,11,2],
   [5,8,4,5]
]
사고방식: 위에서 아래로 귀속되고 귀속하는 과정에서 각 노드의 값을 저장하고sum에서 이 노드의 값을 빼서 새로운sum를 아래로 전달한다.잎 노드로 돌아갈 때 잎 노드와sum가 같으면 지나가는 경로가 요구에 부합되는 경로이다.(요구에 부합되는 모든 경로를 한데 모으기 위해 다음 알고리즘은 인용에 따라 전달되는 변수인vector>&paths를 사용합니다).코드는 다음과 같습니다.
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        // main function
        vector<vector<int>> paths;
        vector<int> path;
        hasPathSumUtil(root, sum, path, paths );
        
        return paths;
    }
    
    bool hasPathSumUtil(TreeNode *root, int sum, vector<int> path, vector<vector<int>>& paths ) {
        // utility function
        
        if(root==NULL) return false;
        
        path.push_back(root->val); // store the nodes along each path
        
        if(root->left==NULL && root->right==NULL) // if we reach a leaf node
            if(root->val == sum)
            {
                paths.push_back(path); // we have find a valid path
                return true;
            }
            else
                return false; // this path is not valid
                
        bool leftHas = hasPathSumUtil(root->left, sum - root->val, path, paths);
        bool rightHas = hasPathSumUtil(root->right, sum - root->val, path, paths);
        if(leftHas || rightHas)
            return true;
        else
            return false;
    }

좋은 웹페이지 즐겨찾기