# 1022. Sum of Root To Leaf Binary Numbers

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: int sumRootToLeaf(TreeNode* root) { int ans = 0; dfs(root, 0, ans); return ans; } private: void dfs(TreeNode* root, int val, int& ans) { if (root == nullptr) return; val = val * 2 + root->val; if (root->left == nullptr && root->right == nullptr) ans += val; dfs(root->left, val, ans); dfs(root->right, val, ans); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int sumRootToLeaf(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); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def sumRootToLeaf(self, root: Optional[TreeNode]) -> int: ans = 0 def dfs(root: Optional[TreeNode], val: int) -> None: nonlocal ans if not root: return val = val * 2 + root.val if not root.left and not root.right: ans += val dfs(root.left, val) dfs(root.right, val) dfs(root, 0) return ans