[LeetCode] 112. Path Sum

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

tree에서 root~leaf 까지의 합이 주어진 값과 일치하는 경우가 있는지 확인하는 문제이다.

학부생 시절 코딩테스트를 준비할 때에는 tree 문제를 아주 많이 풀었으나, 요즘에는 잘 풀지 않아 DFS라는 개념만 기억하고 있었다. 따로 예전의 스킬을 찾아 보지는 않고, 논리에 맞게 생각하면서 분기를 태웠다. 아래가 제출한 코드인데, 분기 코드가 좀 지저분하다. 주어진 TreeNode가 부모는 갖고 있지 않아 stack에 push/pop하면서 비교하고, 한 쪽만 비거나 양 쪽 모두 비었을 경우 모두를 분기하느라 분기 조건이 길어졌다.

이 문제 또한 요즘 C++을 사용하고 있어 문제도 C++로 풀어 보았다.

/**
 * 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) {
        bool result = false;
        if(root == nullptr) {
            return result;
        }

        std::stack<TreeNode*> st;
        st.push(root);
        auto iterNode = st.top();
        TreeNode* popNode = nullptr;
        int sum = tempNode->val;
        int count = 0;
        while(!st.empty()) {
            iterNode = st.top();
            if (iterNode == root) {
                if ((root->left == nullptr && root->right == nullptr) && ++count == 1) {
                    result = (root->val == targetSum);
                    break;
                } else if ((root->left == nullptr || root->right == nullptr) && ++count == 2) {
                    break;
                } else if (++count == 3) {
                    break;
                }
            }
            if(iterNode->left != nullptr && popNode != iterNode->left && (popNode != iterNode->right || popNode == nullptr || iterNode->right == nullptr)) {
                sum += iterNode->left->val;
                st.push(iterNode->left);
                continue;
            } else if(iterNode->right != nullptr && popNode != iterNode->right) {
                sum += iterNode->right->val;
                st.push(iterNode->right);
                continue;
            } else {
                if (sum == targetSum && iterNode->left == nullptr && iterNode->right == nullptr) {
                    result = true;
                    break;
                }
                popNode = st.top();
                sum -= popNode->val;
                st.pop();
            }
        }

        return result;
    }
};

위에서 말했듯이 우선 while문 내에서 stack에 넣고 빼기를 하도록 하고 그 후에 분기들을 붙이느라 여러 케이스들이 많아 조건문이 길고 보기 복잡해졌다.

문제풀이를 가끔씩 하던 터라 감을 잡기 위해 이번에는 따로 공부하지 않고 논리로 풀었으나, 좀 더 간결하게 짤 수 있도록 해야겠다.