LeetCode Solutions
129. Sum Root to Leaf Numbers
Time: $O(n)$ Space: $O(h)$
class Solution {
public:
int sumNumbers(TreeNode* root) {
int ans = 0;
dfs(root, 0, ans);
return ans;
}
private:
void dfs(TreeNode* root, int path, int& ans) {
if (root == nullptr)
return;
if (root->left == nullptr && root->right == nullptr) {
ans += path * 10 + root->val;
return;
}
dfs(root->left, path * 10 + root->val, ans);
dfs(root->right, path * 10 + root->val, ans);
}
};
class Solution {
public int sumNumbers(TreeNode root) {
dfs(root, 0);
return ans;
}
private int ans = 0;
private void dfs(TreeNode root, int path) {
if (root == null)
return;
if (root.left == null && root.right == null) {
ans += path * 10 + root.val;
return;
}
dfs(root.left, path * 10 + root.val);
dfs(root.right, path * 10 + root.val);
}
}
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
ans = 0
def dfs(root: Optional[TreeNode], path: int) -> None:
nonlocal ans
if not root:
return
if not root.left and not root.right:
ans += path * 10 + root.val
return
dfs(root.left, path * 10 + root.val)
dfs(root.right, path * 10 + root.val)
dfs(root, 0)
return ans