BFS_special

102. Binary Tree Level Order Traversal

和下面这道题其实差不多。

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        res, current = [], [root]
        while current:
            nextlevel, subres = [], []
            for node in current:
                subres.append(node.val)
                if node.left:
                    nextlevel.append(node.left)
                if node.right:
                    nextlevel.append(node.right)
            current = nextlevel
            res.append(subres)
        return res

107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        current, result = [root], []
        while current:
            next_level, vals = [], []
            for node in current:
                vals.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            current = next_level
            result.append(vals)
        return result

BFS基本的思想不难，建立一个栈，可以用列表模拟，但是题目一开始不知道如何处理不同的level，上面的方面比较通用。

310. Minimum Height Trees

from collections import defaultdict
class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        neighbor = defaultdict(set)
        for u, v in edges:
            neighbor[u].add(v)
            neighbor[v].add(u)
        res, minheight = [], float("inf")
        for i in xrange(n):
            temp = self.height_helper(n, i, neighbor, minheight)
            if temp == minheight:
                res.append(i)
            if temp < minheight:
                res, minheight = [i], temp
        return res

    def height_helper(self, n, node, neighbor, minheight):
        visited = [False for _ in xrange(n)]
        current, height = [node], 0
        while current:
            next_level = []
            for node in current:
                visited[node] = True
                for item in neighbor[node]:
                    if not visited[item]:
                        next_level.append(item)
            current = next_level
            height += 1
            if height > minheight:
                return float("inf")
        return height

上面的方法超时了，思路没有问题。

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n == 1:
            return [0]

        neighbors = collections.defaultdict(set)
        for u, v in edges:
            neighbors[u].add(v)
            neighbors[v].add(u)

        pre_level, unvisited = [], set()
        for i in xrange(n):
            if len(neighbors[i]) == 1:  # A leaf.
                pre_level.append(i)
            unvisited.add(i)

        # A graph can have 2 MHTs at most.
        # BFS from the leaves until the number 
        # of the unvisited nodes is less than 3.
        while len(unvisited) > 2:
            cur_level = []
            for u in pre_level:
                unvisited.remove(u)
                for v in neighbors[u]:
                    if v in unvisited: 
                        neighbors[v].remove(u)
                        if len(neighbors[v]) == 1:
                            cur_level.append(v)
            pre_level = cur_level
    
        return list(unvisited)

301. Remove Invalid Parentheses

class Solution(object):
    def removeInvalidParentheses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = []
        current = [s]
        visited = set()
        while current:
            nextlevel = []
            for string in current:
                if string in visited:
                    continue
                else:
                    visited.add(string)
                if self.isVaild(string):
                    res.append(string)
                    continue
                for i in range(len(string)):
                    if string[i] not in '()':
                        continue
                    temp = string[:i] + string[i+1:]
                    nextlevel.append(temp)
            if res:
                break
            current = nextlevel
        return res

    def isVaild(self, s):
        if s is None:
            return False
        stack = []
        for char in s:
            if char == '(':
                stack.append('(')
            if char == ')':
                if not stack:
                    return False
                else:
                    stack.pop()

        return stack == []