Tree and Graphs

1 Same Tree

# 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 isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return p == q

2 Validate Binary Search Tree

# 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 isValidBST(self, root, left=-(1<<31+1), right=1<<31):
        """
        :type root: TreeNode
        :rtype: bool
        """

        if not root:
            return True

        if not left < root.val < right:
            return False

        return self.isValidBST(root.left, left, root.val) and self.isValidBST(root.right, root.val, right)

3 Binary Tree Paths

# 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 binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        if not root:
            return []
        return self.helper(root, '', [])


    def helper(self, root, path, res):
        if  not root.left and not root.right:
            res.append(path + str(root.val))
            return res

        if root.left:
            self.helper(root.left, path + str(root.val) + '->', res)
        if root.right:
            self.helper(root.right, path + str(root.val) + '->', res)
        return res

4 Diameter of Binary Tree

# 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 diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0

        s = [root]
        res = 0
        while s:
            tmp = s.pop()
            cur_dia = self.maxDepth(tmp.left) + self.maxDepth(tmp.right)
            res = max(res, cur_dia)
            if tmp.left:
                s.append(tmp.left)
            if tmp.right:
                s.append(tmp.right)
        return res

    def maxDepth(self, root):
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

5 Binary Tree Vertical Order Traversal

# 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 verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []

        s = [(root, 0)]
        dic = collections.defaultdict(list)
        l = r = 0

        while s:
            node, indx = s.pop(0)
            dic[indx].append(node.val)
            l, r = min(l, indx), max(r, indx)
            if node.left:
                s.append((node.left, indx-1))
            if node.right:
                s.append((node.right, indx+1))

        return [ dic[i] for i in range(l, r+1) if i in dic ]

6 Construct Binary Tree from Preorder and Inorder Traversal

# 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 buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not inorder:
            return
        val = preorder.pop(0)
        index = inorder.index(val)
        root = TreeNode(val)
        l = self.buildTree(preorder, inorder[:index])
        r = self.buildTree(preorder, inorder[index+1:])
        root.left = l
        root.right = r
        return root

7 Number of Islands

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0

        r, c = len(grid), len(grid[0])
        cnt = 0
        for i in range(r):
            for j in range(c):
                if grid[i][j] == '1':
                    self.sink(i, j, grid, r, c)
                    cnt += 1
        return cnt

    def sink(self, i, j, grid, r, c):
        s = [(i, j)]
        while s:
            i, j = s.pop()
            grid[i][j] = '0'
            for d, p in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                x, y = i+d, j+p
                if 0 <= x < r and 0 <= y < c and grid[x][y] == '1':
                    s.append((x,y))
        return

8 Clone Graph

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):
        if not node:
            return node
        dic = {}
        stack = [node]
        visited = set()

        # deep copy node
        while stack:
            tmp = stack.pop()
            print(tmp.label, tmp.neighbors)
            visited.add(tmp)
            dic[tmp.label] = UndirectedGraphNode(tmp.label)
            for c in tmp.neighbors:
                if c not in visited:
                    stack.append(c)

        # copy neighbors
        for n in visited:
            for c in n.neighbors:
                dic[n.label].neighbors.append(dic[c.label])

        return dic[node.label]