[Leetcode] 1022. Sum of Root To Leaf Binary Numbers (C++)

문제

1022. Sum of Root To Leaf Binary Numbers

코드

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode* node, int cur){
        if (!node) return 0;
        cur = (cur << 1) | node->val;
        if (!node->left and !node->right) return cur;
        return dfs(node->left, cur) + dfs(node->right, cur);
    }
};

접근

루트 노드부터 리프 노드까지 가서야 어떤 이진수 인지 확인할 수가 있다. 따라서 리프 노드에 도달 했을 때의 값을 반환해야 한다고 생각했고 이에 따라 그때까지 값을 유지해야 한다고 생각했다. 이를 위해서 비트연산을 통해 1칸씩 밀고 현재 노드의 값에 따라서 새로운 값이 결정될 수 있게 하였다. 계산 후 리프 노드라면 바로 현재 값을 반환하고, 아니라면 리프노드까지 갈 수 있게 다시 재귀 호출을 하였다.