Part 4 – 杂鱼

100. Same Tree

https://leetcode.com/problems/same-tree/description/

DFS的一种。注意if语句排他性的巧妙应用。
代码如下：

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

class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

112. Path Sum

https://leetcode.com/problems/path-sum/description/

这道题是树操作的题目，判断是否从根到叶子的路径和跟给定sum相同的。还是用常规的递归方法来做，递归条件是看左子树或者右子树有没有满足条件的路径，也就是子树路径和等于当前sum减去当前节点的值。结束条件是如果当前节点是空的，则返回false，如果是叶子，那么如果剩余的sum等于当前叶子的值，则找到满足条件的路径，返回true。算法的复杂度是树的遍历，时间复杂度是O(n)，空间复杂度是O(logn)。
代码如下：

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

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

树的题目基本都是用递归来解决，主要考虑两个问题：
1）如何把问题分治成子问题给左子树和右子树。这里就是看看左子树和右子树有没有存在和是sum减去当前结点值得路径，只要有一个存在，那么当前结点就存在路径。
2）考虑结束条件是什么。这里的结束条件一个是如果当前节点为空，则返回false。另一个如果是叶子，那么如果剩余的sum等于当前叶子的值，则找到满足条件的路径，返回true。

113. Path Sum II

https://leetcode.com/problems/path-sum-ii/description/

思路和Path Sum是完全一样的，只是需要输出所有路径，所以需要数据结构来维护路径，添加两个参数，一个用来维护走到当前结点的路径，一个用来保存满足条件的所有路径，思路上递归条件和结束条件是完全一致的，空间上这里会依赖于结果的数量了。时间复杂度仍然只是一次遍历O(n)，而空间复杂度则取决于满足条件的路径和的数量（假设是k条），则空间是O(klogn)。
注意，非空判断不是在进入递归前，就是在刚进入递归时，总之要有一个对空的判断，不然会有空指针异常。
代码如下：

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

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        result = []
        self.helper(root, sum, [], result)
        return result
    
    def helper(self, root, sum, path, result):
        if not root:
            return
        if root.val == sum and not root.left and not root.right:
            result.append(list(path+[root.val]))
            return
        self.helper(root.left, sum-root.val, path+[root.val], result)
        self.helper(root.right, sum-root.val, path+[root.val], result)

437. Path Sum III

https://leetcode.com/problems/path-sum-iii/description/

Two Sum Method: Optimized Solution

A more efficient implementation uses the Two Sum idea. It uses a hash table (extra memory of order N). With more space, it gives us an O(N) complexity.
As we traverse down the tree, at an arbitrary node N, we store the sum until this node N (sum_so_far (prefix) + N.val). in hash-table. Note this sum is the sum from root to N.
Now at a grand-child of N, say G, we can compute the sum from the root until G since we have the prefix_sum until this grandchild available.We pass in our recursive routine.
How do we know if we have a path of target sum which ends at this grand-child G? Say there are multiple such paths that end at G and say they start at A, B, C where A,B,C are predecessors of G. Then sum(root->G) - sum(root->A) = target. Similarly sum(root->G)-sum(root>B) = target. Therefore we can compute the complement at G as sum_so_far+G.val-target and look up the hash-table for the number of paths which had this sum.
Now after we are done with a node and all its grandchildren, we remove it from the hash-table. This makes sure that the number of complement paths returned always correspond to paths that ended at a predecessor node.
代码如下：

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

class Solution:
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        self.result = 0
        self.helper(root, sum, 0, {0:1})
        return self.result
    
    def helper(self, root, target, pre_sum, sums):
        if not root:
            return
        cur_sum = pre_sum + root.val
        if cur_sum - target in sums:
            self.result += sums[cur_sum - target]
        sums.setdefault(cur_sum, 0)
        sums[cur_sum] += 1
        self.helper(root.left, target, cur_sum, sums)
        self.helper(root.right, target, cur_sum, sums)
        sums[cur_sum] -= 1

129. Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers/description/

递归到的结点分2种情况：结点为叶子结点，将总和加入到最终结果中去；结点非叶子结点，继续递归其子结点即可。
算法的本质是一次先序遍历，所以时间复杂度是O(n)，空间是栈大小，即O(logn)。
代码如下：

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

class Solution:
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.result = 0
        self.helper(root, 0)
        return self.result
    
    def helper(self, root, num):
        if not root:
            return
        value = num * 10 + root.val
        if not root.left and not root.right:
            self.result += value
            return
        self.helper(root.left, value)
        self.helper(root.right, value)

114. Flatten Binary Tree to Linked List

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/

相当于一个反着的先序遍历。用pre保存上一个访问的结点，然后对当前结点进行处理。
代码如下：

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

class Solution:
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        self.pre = None
        self.helper(root)
        
    def helper(self, root):
        if not root:
            return None
        self.helper(root.right)
        self.helper(root.left)
        root.right = self.pre
        root.left = None
        self.pre = root