258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. 

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up: Could you do it without any loop/recursion in O(1) runtime?

树根问题，参考https://zh.wikipedia.org/wiki/%E6%95%B8%E6%A0%B9

树根的用途：

数根可以计算模运算的同余，对于非常大的数字的情况下可以节省很多时间。

数字根可作为一种检验计算正确性的方法。例如，两数字的和的数根等于两数字分别的数根的和。

另外，数根也可以用来判断数字的整除性，如果数根能被3或9整除，则原来的数也能被3或9整除。

class Solution(object):
    def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num == 0: return 0
        else:
            return num - 9 * ((num - 1) / 9)

258. Add Digits

原文：http://www.cnblogs.com/sxbjdl/p/5221476.html