검지offer-36 두 갈래 나무와 어떤 값의 경로

5312 단어

제목 설명


두 갈래 나무의 루트 노드와 정수를 입력하고 두 갈래 나무의 결점 값과 정수를 입력하는 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.(주의: 값을 되돌려주는list에서 그룹 길이가 큰 그룹이 앞에 있습니다)
 
문제:
일반적으로 트리와 관련된 제목은 DFS와 BFS가 먼저 생각납니다
　　 
 1 class Solution {
 2 public:
 3     vectorint> > FindPath(TreeNode* root, int expectNumber) {
 4         vectorint>>res;
 5         vector<int>v;
 6         DFS(root, expectNumber, 0, v, res);
 7         sort(res.begin(), res.end(), [](vector<int>a, vector<int>b) {
 8             if (a.size() != b.size())return a.size() > b.size();
 9             for (int i = 0; i < a.size(); ++i)
10                 if (a[i] != b[i])
11                     return a[i] > b[i];
12             return a[0] > b[0];
13         });
14         return res;        
15     }
16     void DFS(TreeNode* root, const int N, int sum, vector<int>&v, vectorint>>&res)
17     {
18         if (root == nullptr)return;
19         v.push_back(root->val);// ， ， ， ， 
20         sum += root->val;
21         if (sum >= N)
22         {
23             if (sum == N && root->left == nullptr && root->right == nullptr)// 
24                 res.push_back(v);
25             //return;// ， 
26         }
27         DFS(root->left, N, sum, v, res);
28         DFS(root->right, N, sum, v, res);
29         sum -= root->val;
30         v.pop_back();
31     }
32 };

검지 Offer 알고리즘 구현의 19: 두 갈래 나무의 거울
제목 1368: 두 갈래 나무와 어떤 값의 경로 - 9도

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage