[LeetCode] 1022. Sum of Root To Leaf Binary Numbers c++

• 문제

You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.

• For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.

The test cases are generated so that the answer fits in a 32-bits integer.

Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

tree의 depth별로 만들 수 있는 2진수를 모두 더한 값을 구하는 문제이다.

 

• 문제 해결

int sumRootToLeaf(const TreeNode* r, uint32_t sum = 0) {
    if (!r) return 0;
    sum |= r->val;
    if (!r->left && !r->right) return sum; // leaf
    sum <<= 1;
    return sumRootToLeaf(r->left, sum) + sumRootToLeaf(r->right, sum);
}

sum의 초기 값은 0입니다.

sum은 이전 까지 더한 sum값, r->val은 노드를 이동한 현재  value 값입니다.

 

sum과 r->val 은 OR연산을 해서 더하기 연산을 합니다. (r-val과 1의 자릿수 연산)

→sum은 이전 연산에서 sum << 1한 값으로 자릿수가 하나 올라갔습니다. r-val은 1의 자릿수 입니다.

 

하위 노드가 없다면 sum << 1을 수행합니다.

( sum << 1 ) 는 sum 비트를 왼쪽으로 1자리 이동한다는 의미입니다. 

이는 (sum * 2 )와 같습니다.

 

 

다른 방법1

int ans = 0;

void dfs(TreeNode *root, int buff){
    buff = buff*2 + root->val;
    if(!root->left && !root->right){
        ans += buff;
         return;
     }
     if(root->left) dfs(root->left, buff);
      if(root->right) dfs(root->right, buff);
}

int sumRootToLeaf(TreeNode* root) {
    int buff = 0;
    dfs(root, buff);
        return ans;    
}

 

다른 방법2

 int sumRootToLeaf(TreeNode* rt) {
        if(! rt) return 0;
        
        int ans = 0;
        stack<pair<TreeNode*,int>> st;
        st.push({rt,0});
        
        while(! st.empty()) {
            auto curp = st.top(); st.pop();
            TreeNode* cur = curp.first;
            int cur_val = curp.second;
            
            // Equivalent to left shift by 1 and then ORing by cur->val.
            cur_val = cur_val*2 + cur->val;
            
            if(!cur->left && !cur->right)
                ans += cur_val;
            
            if(cur->left) st.push({cur->left, cur_val});
            if(cur->right) st.push({cur->right, cur_val});
        }
        
        return ans;
}