摘要：求出滿足這樣要求的路徑的數(shù)目，并返回。第二道題給定一個數(shù)，將其拆分為個平方數(shù)的和，求最小的。這道題不能用貪心算法求解。當(dāng)時，如果用貪心算法，結(jié)果就是，返回。假設(shè)給出的數(shù)字為。第三輪減，得到，將放入隊(duì)列中。

第一道題：
給定一棵二叉樹，在二叉樹的所有路徑中找到路徑上結(jié)點(diǎn)之和為題目給定值的子路徑。路徑不一定以根節(jié)點(diǎn)為開頭，也不一定以葉節(jié)點(diǎn)為結(jié)尾。并且根據(jù)分析路徑之間應(yīng)該可以重疊。求出滿足這樣要求的路徑的數(shù)目，并返回。

      10
     /  
    5   -3
   /     
  3   2   11
 /    
3  -2   1

當(dāng)給出以上的二叉樹，并以8為路徑節(jié)點(diǎn)和時，5->3，5->2->1,-3->11三條路徑滿足條件返回三。

對于根節(jié)點(diǎn)來講，滿足條件的路徑，包括以根節(jié)點(diǎn)為起點(diǎn)的路徑，以及不以根節(jié)點(diǎn)為起點(diǎn)的路徑。
我們先定義一個函數(shù)，這個函數(shù)有兩個節(jié)點(diǎn)node和sum，它的含義是，求出從node開始的，路徑上各節(jié)點(diǎn)之和為sum的這樣的路徑的個數(shù)。注意是從node開始的。

result初始化為0。如果當(dāng)前node的value等于sum，則將result加1。由于可能會有負(fù)數(shù)節(jié)點(diǎn)，因此不能立刻返回result，應(yīng)該分別再遞歸的去計(jì)算以node的左孩子和右孩子為起點(diǎn)，和為sum-node.value的路徑的數(shù)目。
代碼如下：

    def path_num_from(self, node, sum):
        if node is None:
            return 0

        res = 0
        if node.val == sum:
            res += 1

        res += self.path_num_from(node.left, sum - node.val)
        res += self.path_num_from(node.right, sum - node.val)

        return res

之前已經(jīng)提到過，本題所求的路徑不僅包含以根節(jié)點(diǎn)為起點(diǎn)的路徑，還包含不以根節(jié)點(diǎn)為起點(diǎn)的路徑。因此我們再定義一個函數(shù)，來算出，包含根節(jié)點(diǎn)的路徑，和不包含根節(jié)點(diǎn)的路徑。

    def __pathSum(self, node, sum):
        if node is None:
            return 0

        return self.find_path(node, sum) + self.__pathSum(node.left, sum) + self.__pathSum(node.right, sum)

題目得解。

第二道題：
給定一個數(shù)，將其拆分為n個平方數(shù)的和，求最小的n。
例如13 = 9 + 4 13 = 9 + 1 + 1 + 1 + 1
13是9和4兩個平方數(shù)的和，也是9和4個1的和（如果用重復(fù)，按出現(xiàn)的次數(shù)計(jì)數(shù)，1計(jì)數(shù)4次而不是1次），因?yàn)?小于5，所以返回2。

這道題不能用貪心算法求解。
當(dāng)n=12時，如果用貪心算法，結(jié)果就是9+1+1+1，返回4。但是更優(yōu)的解是4+4+4，返回3。

假設(shè)給出的數(shù)字為n。先建立一個set。set中存放所有的，小于n的平方數(shù)。
比如給出數(shù)字13時，set中添加1,4,9。因?yàn)?6大于13，所以不添加。
以15舉例。set為 1,4,9。建立一個隊(duì)列。

第一輪：
15減去9，得到6。將6放入隊(duì)列中。
15減去4，得到11。將11放入隊(duì)列中。
15減去1，得到14，將14放入隊(duì)列中。
第一輪遍歷完畢。此時隊(duì)列中還有6,11,14

第二輪：
6比9小，所以不能再減9。
6減4，得到2，將2放入隊(duì)列中。
6減1，得到5，將5放入隊(duì)列中。
11減9，得到2，將2放入隊(duì)列中。
11減4，得到7，將7放入隊(duì)列中。
11減1，得到10，將10放入隊(duì)列中。
第二輪遍歷完畢。去掉重復(fù)的數(shù)，此時隊(duì)列中還有2,5,7,10。

第三輪：
2減1，得到1，將1放入隊(duì)列中。
5減4，得到1，將1放入隊(duì)列中。
5減1，得到4，將4放入隊(duì)列中。
7減4，得到3，將3放入隊(duì)列中。
7減1，得到6，將6放入隊(duì)列中。
10減4，得到6，將6放入隊(duì)列中。
10減1，得到9，將9放入隊(duì)列中。
第三輪遍歷完畢。去掉重復(fù)元素，此時隊(duì)列中還有1,3,4,6,9。

第四輪：
1減1，得到0。結(jié)束循環(huán)。直接返回此時層數(shù)。由于遍歷了四輪，因此返回4。

代碼如下：

 def numSquares(self, n):
        nums_to_subtract = []
        i = 1
        while i**2 <= n:
            nums_to_subtract.append(i**2)
            i += 1

        depth = 0
        current_level_nodes = {n}

        while True:
            nodes = current_level_nodes
            current_level_nodes = set()
            depth += 1
            for num_left in nodes:
                for num in nums_to_subtract:
                    if num_left < num:
                        break
                    elif num_left > num:
                        current_level_nodes.add(num_left - num)
                    else:
                        return depth