112. Path Sum [Easy]

https://leetcode.com/problems/path-sum/

Path Sum - LeetCode

 

이진 트리의 루트와 목표 합이 주어졌을 때, root부터 leaf 노드까지 모든 노드의 합이 목표 계와 동일한지 판단하는 문제다.

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return false;
        }
        
        if (!root->left && !root->right) {
            return root->val == targetSum;
        }
        
        return hasPathSum(root->left, targetSum - root->val) ||
            hasPathSum(root->right, targetSum - root->val);
    }
};

 

 

 

처음에 한 번 풀고, 다른 분이 Runtime을 줄여보라고 해서 일부 코드 순서만 바꿨는데 반으로 줄었다.

이해가 안가서 각각 소스 코드를 어셈블리로 봤는데... 명령어 양은 크게 차이없는거 같은데 그저 그때그때 리소스 따라 반응 속도가 다른것인가 싶다.. 그래도 반타작은 너무한데..

 

이하 40ms

bool hasPathSum(TreeNode* root, int targetSum) {
00CF2AE0  push        ebp  
00CF2AE1  mov         ebp,esp  
00CF2AE3  sub         esp,0C4h  
00CF2AE9  push        ebx  
00CF2AEA  push        esi  
00CF2AEB  push        edi  
00CF2AEC  lea         edi,[ebp-0C4h]  
00CF2AF2  mov         ecx,31h  
00CF2AF7  mov         eax,0CCCCCCCCh  
00CF2AFC  rep stos    dword ptr es:[edi]  
00CF2AFE  mov         ecx,offset _C639023A_Main@cpp (0CFF091h)  
00CF2B03  call        @__CheckForDebuggerJustMyCode@4 (0CF142Eh)  
    if (nullptr == root) {
00CF2B08  cmp         dword ptr [root],0  
00CF2B0C  jne         NodeSum+15h (0CF2B15h)  
        return false;
00CF2B0E  xor         al,al  
00CF2B10  jmp         NodeSum+0A9h (0CF2BA9h)  
    }

    if (nullptr != root->left || nullptr != root->right) {
00CF2B15  mov         eax,dword ptr [root]  
00CF2B18  cmp         dword ptr [eax+4],0  
00CF2B1C  jne         NodeSum+27h (0CF2B27h)  
00CF2B1E  mov         eax,dword ptr [root]  
00CF2B21  cmp         dword ptr [eax+8],0  
00CF2B25  je          NodeSum+83h (0CF2B83h)  
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
00CF2B27  mov         eax,dword ptr [root]  
00CF2B2A  mov         ecx,dword ptr [targetSum]  
00CF2B2D  sub         ecx,dword ptr [eax]  
00CF2B2F  push        ecx  
00CF2B30  mov         edx,dword ptr [root]  
00CF2B33  mov         eax,dword ptr [edx+4]  
00CF2B36  push        eax  
00CF2B37  call        hasPathSum (0CF116Dh)  
00CF2B3C  add         esp,8  
00CF2B3F  movzx       ecx,al  
00CF2B42  test        ecx,ecx  
00CF2B44  jne         NodeSum+71h (0CF2B71h)  
00CF2B46  mov         edx,dword ptr [root]  
00CF2B49  mov         eax,dword ptr [targetSum]  
00CF2B4C  sub         eax,dword ptr [edx]  
00CF2B4E  push        eax  
00CF2B4F  mov         ecx,dword ptr [root]  
00CF2B52  mov         edx,dword ptr [ecx+8]  
00CF2B55  push        edx  
00CF2B56  call        hasPathSum (0CF116Dh)  
00CF2B5B  add         esp,8  
00CF2B5E  movzx       eax,al  
00CF2B61  test        eax,eax  
00CF2B63  jne         NodeSum+71h (0CF2B71h)  
00CF2B65  mov         dword ptr [ebp-0C4h],0  
00CF2B6F  jmp         NodeSum+7Bh (0CF2B7Bh)  
00CF2B71  mov         dword ptr [ebp-0C4h],1  
00CF2B7B  mov         al,byte ptr [ebp-0C4h]  
00CF2B81  jmp         NodeSum+0A9h (0CF2BA9h)  
    }

    return targetSum == root->val;
00CF2B83  mov         eax,dword ptr [root]  
00CF2B86  mov         ecx,dword ptr [targetSum]  
00CF2B89  cmp         ecx,dword ptr [eax]  
00CF2B8B  jne         NodeSum+99h (0CF2B99h)  
00CF2B8D  mov         dword ptr [ebp-0C4h],1  
00CF2B97  jmp         NodeSum+0A3h (0CF2BA3h)  
00CF2B99  mov         dword ptr [ebp-0C4h],0  
00CF2BA3  mov         al,byte ptr [ebp-0C4h]  
}

 

 

이하 20ms

bool hasPathSum(TreeNode* root, int targetSum) {
004D2AE0  push        ebp  
004D2AE1  mov         ebp,esp  
004D2AE3  sub         esp,0C4h  
004D2AE9  push        ebx  
004D2AEA  push        esi  
004D2AEB  push        edi  
004D2AEC  lea         edi,[ebp-0C4h]  
004D2AF2  mov         ecx,31h  
004D2AF7  mov         eax,0CCCCCCCCh  
004D2AFC  rep stos    dword ptr es:[edi]  
004D2AFE  mov         ecx,offset _C639023A_Main@cpp (04DF091h)  
004D2B03  call        @__CheckForDebuggerJustMyCode@4 (04D142Eh)  
    if (nullptr == root) {
004D2B08  cmp         dword ptr [root],0  
004D2B0C  jne         NodeSum+15h (04D2B15h)  
        return false;
004D2B0E  xor         al,al  
004D2B10  jmp         NodeSum+0A9h (04D2BA9h)  
    }

    if (nullptr == root->left && nullptr == root->right) {
004D2B15  mov         eax,dword ptr [root]  
004D2B18  cmp         dword ptr [eax+4],0  
004D2B1C  jne         NodeSum+4Fh (04D2B4Fh)  
004D2B1E  mov         eax,dword ptr [root]  
004D2B21  cmp         dword ptr [eax+8],0  
004D2B25  jne         NodeSum+4Fh (04D2B4Fh)  
        return targetSum == root->val;
004D2B27  mov         eax,dword ptr [root]  
004D2B2A  mov         ecx,dword ptr [targetSum]  
004D2B2D  cmp         ecx,dword ptr [eax]  
004D2B2F  jne         NodeSum+3Dh (04D2B3Dh)  
004D2B31  mov         dword ptr [ebp-0C4h],1  
004D2B3B  jmp         NodeSum+47h (04D2B47h)  
004D2B3D  mov         dword ptr [ebp-0C4h],0  
004D2B47  mov         al,byte ptr [ebp-0C4h]  
004D2B4D  jmp         NodeSum+0A9h (04D2BA9h)  
    }

    return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
004D2B4F  mov         eax,dword ptr [root]  
004D2B52  mov         ecx,dword ptr [targetSum]  
004D2B55  sub         ecx,dword ptr [eax]  
004D2B57  push        ecx  
004D2B58  mov         edx,dword ptr [root]  
004D2B5B  mov         eax,dword ptr [edx+4]  
004D2B5E  push        eax  
004D2B5F  call        hasPathSum (04D116Dh)  
004D2B64  add         esp,8  
004D2B67  movzx       ecx,al  
004D2B6A  test        ecx,ecx  
004D2B6C  jne         NodeSum+99h (04D2B99h)  
004D2B6E  mov         edx,dword ptr [root]  
004D2B71  mov         eax,dword ptr [targetSum]  
004D2B74  sub         eax,dword ptr [edx]  
004D2B76  push        eax  
004D2B77  mov         ecx,dword ptr [root]  
004D2B7A  mov         edx,dword ptr [ecx+8]  
004D2B7D  push        edx  
004D2B7E  call        hasPathSum (04D116Dh)  
004D2B83  add         esp,8  
004D2B86  movzx       eax,al  
004D2B89  test        eax,eax  
004D2B8B  jne         NodeSum+99h (04D2B99h)  
004D2B8D  mov         dword ptr [ebp-0C4h],0  
004D2B97  jmp         NodeSum+0A3h (04D2BA3h)  
004D2B99  mov         dword ptr [ebp-0C4h],1  
004D2BA3  mov         al,byte ptr [ebp-0C4h]  
}