Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.

递归法

复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

简单的二叉树遍历，遍历时将自身的数值加入子节点。比如节点A的值是1，其左子节点的值是2，则将左子节点变为12。一旦遍历到叶子节点便将该叶子结点的值加入结果中。

代码

public class Solution {
    
    int sum = 0;
    
    public int sumNumbers(TreeNode root) {
        if(root != null) getSum(root);
        return sum;
    }
    
    private void getSum(TreeNode n){
        if(n.left == null && n.right == null){
            sum += n.val;
        }
        if(n.left != null){
            n.left.val += n.val * 10;
            getSum(n.left);
        }
        if(n.right != null){
            n.right.val += n.val * 10;
            getSum(n.right);
        }
    }
}