# Sum Root to Leaf Numbers

ID: 1353; medium; 根节点到叶节点求和

## Solution 1 (Java)

``````/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/

public class Solution {
/**
* @param root: the root of the tree
* @return: the total sum of all root-to-leaf numbers
*/
public int sumNumbers(TreeNode root) {
if (root == null) return 0;
return dfs(root, 0);
}

private int dfs(TreeNode root, int num) {
if (root == null) return 0;
num = num * 10 + root.val;
if (root.left == null && root.right == null)
return num;
int leftNum = dfs(root.left, num);
int rightNum = dfs(root.right, num);
return leftNum + rightNum;
}
}``````

### Notes

• Divide and conquer

## Solution 2 (Java)

``````/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/

public class Solution {

private int sum = 0;

/**
* @param root: the root of the tree
* @return: the total sum of all root-to-leaf numbers
*/
public int sumNumbers(TreeNode root) {
if (root == null) return sum;
dfs(root, root.val);
return sum;
}

private void dfs(TreeNode root, int num) {
if (root == null) return;
if (root.left == null && root.right == null) {
sum += num;
return;
}
if (root.left != null)
dfs(root.left, num * 10 + root.left.val);
if (root.right != null)
dfs(root.right, num * 10 + root.right.val);
}
}``````

• Traversal

Last updated