Sum Root to Leaf Numbers -- LeetCode

原题链接: http://oj.leetcode.com/problems/sum-root-to-leaf-numbers/
这是一道树的题目，一般使用递归来做，主要就是考虑递归条件和结束条件。这道题思路还是比较明确的，目标是把从根到叶子节点的所有路径得到的整数都累加起来，递归条件即是把当前的sum乘以10并且加上当前节点传入下一函数，进行递归，最终把左右子树的总和相加。结束条件的话就是如果一个节点是叶子，那么我们应该累加到结果总和中，如果节点到了空节点，则不是叶子节点，不需要加入到结果中，直接返回0即可。算法的本质是一次先序遍历，所以时间是O(n)，空间是栈大小，O(logn)。代码如下：

public int sumNumbers(TreeNode root) {
    return helper(root,0);
}
private int helper(TreeNode root, int sum)
{
    if(root == null)
        return 0;
    if(root.left==null && root.right==null)
        return sum*10+root.val;
    return helper(root.left,sum*10+root.val)+helper(root.right,sum*10+root.val);
}

树的题目在LeetCode中还是有比较大的比例的，不过除了基本的递归和非递归的遍历之外，其他大部分题目都是用递归方式来求解特定量，大家还是得熟悉哈。