437. 路径总和 III

方法1:递归

递归时，想清楚：

这个函数是干什么的？不要跳进递归，没用。

这个函数参数中的变量是什么？（函数的参数中可以传递这个变量）

得到函数的递归结果，你应该干什么（比如前序、中序、后序等…）

明白一个递归函数的作用并相信它能完成这个任务，千万不要试图跳进细节
补充递归结束的条件
pathSum(self, root, sum) : 给定root 和目标值，返回和为目标值的路径总数。选择时，有两种情况：路径开始时，选择当前节点/不选择当前节点，只考虑左右孩子
- 结果由3部分构成：以自己开头+（不以自己开头，只考虑左孩子）+ （不以自己开头，只考虑右孩子）
- 以自己开头时，count(self,root,sum): 返回count的个数（能凑出几个以该节点为路径开头，和为目标值的路径总数）
  - 结果由3部分构成：自己独挡一面+（自己出力+左孩子出力）+（自己出力+右孩子出力）

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        # 注意递归结束条件
        if not root: return 0

        # 左边路径总数（相信他能算出来），后序遍历：左
        l=self.pathSum(root.left,sum)
        # 右边路径总数（相信他能算出来），后修遍历：右
        r=self.pathSum(root.right,sum)
        # 自己为开头的路径数，后序遍历：中
        ro=self.count(root,sum)
        res=ro+l+r
        return res

    # 返回count的个数 （能凑出几个以该节点为路径开头，和为目标值的路径总数）
    def count(self,root,sum):
        # 注意递归结束条件
        if not root: return 0
        # 我自己能不能独当一面，作为一条单独的路径呢？
        isMe=1 if root.val==sum else 0
        # 左边的小老弟，你那边能凑几个sum - node.val 呀？
        lc=self.count(root.left,sum-root.val)
        # 右边的小老弟，你那边能凑几个sum - node.val 呀？
        rc=self.count(root.right,sum-root.val)
        # 以我这个头开始的节点，能凑这么多个
        countAll=isMe+lc+rc
        return countAll

方法2:前缀和、回溯算法与哈希表的综合运用

用字典保存累加和的次数，注意有回溯的步骤

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def pathSum(self, root, targetSum):
        """
        :type root: TreeNode
        :type targetSum: int
        :rtype: int
        """
        from collections import defaultdict
        dic=defaultdict(int)
        dic[0]=1
        self.res=0

        def dfs(root,curSum):
            # 递归结束的条件
            if not root:
                return

            curSum+=root.val # 改变当前的前缀和
            if curSum-targetSum in dic: # 类似两数之和的思想，如果curSum-targetSum已经存在字典中，则更新self.res
                self.res+=dic[curSum-targetSum]
            dic[curSum] += 1  # 当前前缀和存到字典中

            dfs(root.left,curSum)
            dfs(root.right,curSum)
            dic[curSum] -=1 # 回溯，减少当前前缀和出现的次数
        dfs(root,0)
        return self.res

盖房子

在某一个点盖一个红房子，之后每个月都在上一次盖的新房子左边盖一个绿房子（G），右边盖一个红房子(R)（不考虑间隔,房子之间距离很大）
输入一个n，表示经过n轮以后，从左到右打印房子的排列。第一个房子为R
输入1
输出 R
输入 2
输出 GRR
输入3
输出 GGRRGRR

用递归方法解决，不要跳进递归中

递归函数的含义：给定一个根节点（子树的根节点的颜色可能为’G’/ ‘R’），返回该节点对应的盖房子结果
- 相信递归函数可以返回我需要的信息
- 因为递归过程中，根节点的颜色是一个变量（有G和R两种），因此用一个helper函数中的color来记录这个信息
注意递归终止的条件（否则会陷入死循环）
- 当n为1时，说明已经到了最下面的叶子节点了，需要return这个叶子结果了
得到递归结果后，应该干什么：可理解为二叉树的中序遍历：左子树helper(n-1,’G’)+中间节点color+右子树helper(n-1,’R’)

n=int(input())

def house(n):
    # 用helper函数记录额外的"头结点"信息
    # 相信这个函数可以返回我需要的信息
    def helper(n,color):
        if n==1: # 递归结束时，返回"头结点"
            return color
        else:
            # 返回左子树的结果+"头结点"+右子树的结果
            return helper(n-1,'G')+color+helper(n-1,'R')
    return helper(n,'R') 
res=house(n)
print(res)