This is the 17th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Hello, everyone, today is the 17th day I participated in the August more text, today brings you about the binary tree related algorithm problem is to find the binary tree from the root to the leaf of the binary number sum, the text is as follows:

The title

I’m going to give you a binary tree where every node has a value of 0 or 1. Each path from the root to the leaf represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then it represents the binary number 01101, which is 13.

For each leaf on the tree, we need to find the number represented by the path from the root to that leaf.

Returns the sum of these numbers. The question data guarantees that the answer is a 32-bit integer.

Example 1 

Input: root = [1,0,1, 1,0,1,0,1,0,1,1, 1, 1, 1, 1, 1, 1, 1, 1] output: 22Copy the code

** Example 2 **

Input: root = [0] Output: 0 Input: root = [1] Output: 1 Input: root = [1] Output: 3Copy the code

Their thinking

Depending on what they mean, we can solve this problem recursively.

Recursive Trilogy:

  1. Recursive function arguments and return values: the function arguments are the nodes passed in and a value to record the current path sum; Since the entire tree is searched, the recursive function does not need to return a value;

  2. Termination condition of recursive function: returns if the node is null

  3. Single-layer logic for recursive functions: if a leaf node is encountered, put the path and in the return value, otherwise continue the depth-first search for left and right child nodes;

Code implementation


/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
 
class Solution {
    // The return value used to return
    private int sum = 0;

    public int sumRootToLeaf(TreeNode root) {
        dfs(root, 0);
        return sum;
    }

    private void dfs(TreeNode root, int curr) {
        // If you encounter a null node, do nothing and return
        if (root == null) return;
        // Add the value of the current node to the current path
        curr = (curr << 1) + root.val;
        // If a leaf node is encountered, put the path sum in the return value
        if (root.left == null && root.right == null) sum += curr;
        // Continue the depth-first search for left and right child nodesdfs(root.left, curr); dfs(root.right, curr); }}Copy the code

The last

Complexity analysis:

  • Time complexity: O(n). Where n is the depth of the tree.
  • Space complexity: O(n). The stack space required for recursion is n.