leetcode || 112、Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example:
Given the below binary tree and
sum = 22 , 5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path
5->4->11->2 which sum is 22. Hide Tags
Tree Depth-first Search
제목: 두 갈래 나무 뿌리 노드가 잎의 모든 경로에 존재하는지, 하나의 경로의 수치와 지정한 수sum가 있는지 검사합니다
thinking:
(1) DFS 사상은 아이 노드를 두루 돌아다니며 결점 수치와 잎 노드에 도달했을 때(좌우 아이가 비어 있음)sum와 크기를 비교한다
(2) 잎 노드에 도달하기 전에 수치와'=sum이면 검색을 끝내고 검색을 가속화하는 역할을 해야 한다고 고려했다.그러나 결점 데이터가 모두 음수이면 적합하지 않다.
그러니까 전면적으로 생각해야 돼.
code:
class Solution {
private:
bool flag;
public:
bool hasPathSum(TreeNode *root, int sum) {
flag=false;
if(root==NULL)
return false;
dfs(0,sum,root);
return flag;
}
protected:
void dfs(int add, int sum, TreeNode *node)
{
if(flag==true)
return;
add+=node->val;
if(node->left==NULL && node->right==NULL)
{
if(add==sum)
flag=true;
return;
}
// if(add>=sum)
// return;
if(node->left!=NULL)
dfs(add,sum,node->left);
if(node->right!=NULL)
dfs(add,sum,node->right);
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
