LeetCode 문제풀이 노트 112.경로 합계

8922 단어

112. 경로 총

  • 제목 요구 사항
  • 문제풀이
  • 교체
  • 귀속

  • 제목 요구


    두 갈래 나무와 목표를 정하고 이 나무에 뿌리 노드가 잎 노드까지의 경로가 있는지 판단한다. 이 경로에 있는 모든 노드 값은 목표와 같다.
    설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
    예: 다음과 같은 두 갈래 트리와 목표와sum=22,

    풀다


    교체하다


    번역자:https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-by-leetcode/
    class Solution {
         
    public:
        bool hasPathSum(TreeNode* root, int sum) {
         
            if(!root) return false;
            
            stack<pair<TreeNode*,int>> s;
            s.push(make_pair(root,sum-root->val));
    
            while(!s.empty()){
         
                TreeNode *node=s.top().first;
                int curSum=s.top().second;
                s.pop();
    
                if(!node->right&&!node->left&&curSum==0) return true;
                if(node->left){
         
                    s.push(make_pair(node->left,curSum-node->left->val));
                }
                if(node->right){
         
                    s.push(make_pair(node->right,curSum-node->right->val));
                }
            }
            return false;
        }
    };
    

    https://github.com/soulmachine/leetcode

    차례로 돌아가다

    class Solution {
         
    public:
        bool hasPathSum(TreeNode* root, int sum) {
         
            if(!root) return false;
            if(!root->left&&!root->right)
                return sum==root->val;
            return hasPathSum(root->left,sum-root->val)
                ||hasPathSum(root->right,sum-root->val);
        }
    };
    

    좋은 웹페이지 즐겨찾기