1022. Sum of Root To Leaf Binary Numbers

EasyView on LeetCode

Tree Depth-First Search Binary Tree

Time: O(n)

Space: O(n)

Intuition

DFS tracking current binary value. At leaf: add value to sum. Pass accumulated value down.

Algorithm

1DFS(node, cur): cur = cur*2 + node.val.
2If leaf: sum += cur. Else recurse on children.

Common Pitfalls

•Leaf = both children null. Pass value as parameter.

1022.cs

// Approach: DFS accumulating the binary number from root to leaf; add the leaf value to the running sum.
// Time: O(n) Space: O(n)

public class TreeNode(TreeNode root)
    {
        DFS(root, 0);
        return ans;
    }

    private int ans = 0;

    private void DFS(TreeNode root, int val)
    {
        if (root == null)
            return;

        val = val * 2 + root.val;
        if (root.left == null && root.right == null)
            ans += val;

        DFS(root.left, val);
        DFS(root.right, val);
    }
}

Was this solution helpful?