두 갈래 트리 중 한 경로에 대한 값(DFS)
5715 단어 데이터 구조와 알고리즘DFS
bool hasPathSum(TreeNode* root, int sum) {
if(root == nullptr)
return false;
if(root->val == sum && root->left == NULL && root->right == NULL)
return true;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
두 갈래 나무 중화는 가치 있는 경로이다
두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
void DFS(TreeNode *root, int sum, vector<int> &path, vector<vector<int>> &paths) {
// 、 nullptr,
if (root == nullptr)
return;
path.push_back(root->val);
if (root->left == nullptr && root->right == nullptr && root->val == sum)
paths.push_back(path);
DFS(root->left, sum - root->val, path, paths);
// nullptr, return;
DFS(root->right, sum - root->val, path, paths);
//
path.pop_back();
}
vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
vector<vector<int>> paths;
vector<int> path;
DFS(root, expectNumber, path, paths);
return paths;
}
또는
void DFS(TreeNode *root, int sum, vector<int> path, vector<vector<int>> &paths){
if(root == nullptr)
return;
path.push_back(root->val);
if(root->left == nullptr && root->right == nullptr && root->val == sum)
paths.push_back(path);
DFS(root->left, sum - root->val, path, paths);
DFS(root->right, sum - root->val, path, paths);
}
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<vector<int>> paths;
vector<int> path;
DFS(root, expectNumber, path, paths);
return paths;
}
동일:https://leetcode.com/problems/binary-tree-paths/description/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.