Sum of binary numbers from root to leaf

1022. Sum of binary numbers from root to leaf

The difficulty is simple 212

Give me a binary tree , The value of each node on it is 0 or 1 . Each path from root to leaf represents a binary number starting from the most significant bit .

• for example , If the path is 0 -> 1 -> 1 -> 0 -> 1, Then it represents a binary number 01101, That is to say 13 .

For every leaf on the tree , We all have to find the number represented by the path from the root to the leaf .

Returns the sum of these numbers . The question data guarantees that the answer is 32 position Integers .

Example 1：

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

Example 2：

 Input ：root = [0]
 Output ：0 

Tips ：

• The number of nodes in the tree is [1, 1000] Within the scope of
• Node.val Only for 0 or 1

---

Ideas ： Recursive postorder traversal

​ You need to traverse the binary tree , The first thing to think about is recursion , Break big problems into small ones , Let the left and right subtrees complete the task respectively , Recursion in turn , Until I met nullptr.

• Because we need to count the total , So it defines a Global variables sum , And considering that recursion to the left and right subtrees also needs to pass the sum of the values of the current path , therefore Create a new sub function to complete recursion , Set the parameter to root and val,val Represents the sum of all paths before encountering the current node .
• Then continue the post order traversal ：
  • If the current node Is a leaf node , Will val The value is assigned to sum, And back to .
  • If the current node Is a non leaf node , Then continue to recurse to the left and right subtrees .

/** * 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:
    int sum = 0;
    int _sumRootToLeaf(TreeNode* root, int val)
    {
    
        if(root == nullptr)
            return 0;

        val = root->val + (val << 1);
        _sumRootToLeaf(root->left, val);
        _sumRootToLeaf(root->right, val);

        // If it's a leaf node , Then let sum Add the sum of this path 
        if(root->left == nullptr && root->right == nullptr)
            sum += val;
        return sum;
    }
    int sumRootToLeaf(TreeNode* root) {
    
        return _sumRootToLeaf(root, 0);
    }
};

Complexity

• Time complexity ：O(N),N Is the number of binary tree nodes .
• Spatial complexity ：O(N), Stack space used by recursion .