Day13

昨天又放飞了自我一天，去看望了好友及其丈夫，好友说“觉得自己很幸运，父母当初送自己出来读大学，让自己能找到一份轻松的工作，体面的薪水”。虽然每月五千不是我的理想值，但道理是相同的道理。在学生阶段，是价值的跃升期，你多付出一分，未来的生活就会更美好一分，这都是唾手可见的。也许我不该再这么肆意妄为了，我看到弟弟的微博，每一条都是在如何更加努力，他并不是天才，他得到现在的成绩，也是靠着一分一分努力而来的。还是少玩点，多努力点吧，上天会看到你的付出的。

111. Minimum Depth of Binary Tree
     **思路：终于会自己写递归函数了，但是有一点没搞清楚，最短路径的前提是存在子节点，所以在某个子节点的子节点不存在时，不能再算一条路径了。

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0

        if not root.left:
            return 1+self.minDepth(root.right)
        elif not root.right:
            return 1+self.minDepth(root.left)
        else:
            return 1+min(self.minDepth(root.left),self.minDepth(root.right))

112. Path Sum
     **思路：开始想到了剪枝算法，不喜欢用BFS,继续用DFS吧。题目希望找到满足SUM的这么一条从根节点到叶子的路径。整数可以有负数，所以剪枝用不到。

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root == None:
            return False
        if root.left == None and root.right == None:
            return root.val == sum
        return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)