August 10, 2019

129. Sum Root to Leaf Numbers

写法1. Recursive

Time = O(n).
Space = O(h) to keep the recursion stack, where h is a tree height.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private int totalSum = 0;
    
    public int sumNumbers(TreeNode root) {
        sumNumbers(root, 0);
        return totalSum;
    }
    
    private void sumNumbers(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null) {
            totalSum += sum;
        }
        sumNumbers(root.left, sum);
        sumNumbers(root.right, sum);
    }
}

写法2. Recursive - divide and conquer

参考[这个题解](https://www.cnblogs.com/grandyang/p/4273700.html）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        return sumNumbersHelper(root, 0);
    }
    
    private int sumNumbersHelper(TreeNode root, int sum) {
        if (root == null) {
            return 0; // 遍历到叶结点了，就将当前的累加结果sum返回。
        }
        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        }
        return sumNumbersHelper(root.left, sum) + sumNumbersHelper(root.right, sum); // 对其左右子结点分别调用递归函数
    } 
}