leetcode 129. 求根到叶子节点数字之和

题目描述

给定一个二叉树，它的每个结点都存放一个0-9的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
相关话题： 树、深度优先搜索    难度： 中等

示例1：

示例2：

思路：

• 首先是先序遍历，每遍历到一个节点，如果该节点不是null，用传进来的sum * 10 + 当前节点的值sum = sum * 10 + root.val;当当前节点是叶子节点，返回sum，这就是一条路径的值。这是递归的子问题
• 递归左、右子树，返回左右子树的值的和。
  return sumNumbers(root.left,sum) + sumNumbers(root.right,sum);

/**
 * 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 sumNumbers(root, 0);
    }
    public int sumNumbers(TreeNode root, int sum){
        if(root == null) return 0;
        sum = sum * 10 + root.val;
        if(root.left == null && root.right == null)
            return sum;
        return sumNumbers(root.left,sum) + sumNumbers(root.right,sum);
    }
}

总结：递归算法将大问题看小的思路实在是在奇妙了。

• 在做递归的题时，有时候我们需要另起一个函数，然后在另一个函数中调用。例如本题另起了一个函数sumNumbers(TreeNode root, int sum)。因为在算一条路径的值时，是一种自顶向下的递归，必须接受上一步传递下来的结果，是一步一步更新的过程，所以需要sum的辅助。而在做斐波那契数列时，那是一个自底向上的递归，例如要算f(n)，就要知道f(n-1)，一直推到f(1)，在此之前并没有结果算出来。
• 二叉树的递归离不开左、右子树，根据实际问题需要确定子问题， 每个遍历到每个节点所需要做的操作(sum = sum * 10 + root.val)，以及递归返回的条件(叶子节点时返回结果sum)，然后就是借助左右思想return sumNumbers(root.left,sum) + sumNumbers(root.right,sum);。
  做什么操作，什么时候返回