Force deduction solution summary 1022- sum of binary numbers from root to leaf

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ：

Power button

describe ：

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 

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  Recursively traverse all nodes . Every time you traverse a node , Accept the accumulated value passed from the root node , Then add the current value to find the value of the current node .
*  If the node is a leaf node , The calculation SUM value .
*  If not , Pass the value of the current node and recurse .

Code ：

public class Solution1022 {
    int sum = 0;
    public int sumRootToLeaf(TreeNode root) {
        ergodic(root, 0);
        return sum;
    }

    private void ergodic(TreeNode root, int i) {
        int current = (i << 1) + root.val;
        if (root.right == null && root.left == null) {
            sum += current;
            return;
        }
        if (root.left != null) {
            ergodic(root.left, current);
        }
        if (root.right != null) {
            ergodic(root.right, current);
        }
    }
}