Introduction

In this blog post, we will explore how to solve the LeetCode problem "1022" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: Input: root = [1,0,1,0,1,0,1] Output: 22 Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22 Example 2: Input: root = [0] Output: 0 Constraints: The number of nodes in the tree is in the range [1, 1000]. Node.val is 0 or 1.

Explanation

Here's a solution to the problem:

• Depth-First Search (DFS): Traverse the binary tree using DFS to explore all root-to-leaf paths.
• Path Value Calculation: Maintain the value of the path from the root to the current node. Update the path value by left-shifting the current value by 1 and adding the node's value.

• Summation: When a leaf node is reached, add the path value to a running sum.

• Time Complexity: O(N), where N is the number of nodes in the tree.

• Space Complexity: O(H), where H is the height of the tree (call stack for recursion). In the worst case (skewed tree), H = N. In the best case (balanced tree), H = logN.

Code

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sumRootToLeaf(root: TreeNode) -> int:
    def dfs(node, current_val):
        if not node:
            return 0

        current_val = (current_val << 1) | node.val

        if not node.left and not node.right:
            return current_val

        return dfs(node.left, current_val) + dfs(node.right, current_val)

    return dfs(root, 0)