Tree & Graph Structure and Algorithms

Binary Search Tree

Preorder Traversal

def preorderTraversal(self, root):
    res = []
    if root == None:
        return res
    stack = [root]
    while stack:
        root = stack.pop()
        res.append(root.val)
        if root.right:
            stack.append(root.right)
        if root.left:
            stack.append(root.left)
    return res

Inorder Traversal

def inorderTraversal(self, root):
    res = []
    stack = []
    p = root
    while p or stack:
        while p: stack.append(p); p = p.left
        p = stack.pop()
        res.append(p.val)
        p = p.right
    return res

Postorder Traversal (*)

def postorderTraversal(self, root):
    stack = []; res = []
    pre = None
    while root or stack:
        if root:
            stack.append(root)
            root = root.left
        elif pre == stack[-1].right:
            pre = stack.pop()
            res.append(pre.val)
        else:
            root = stack[-1].right
            pre = None
    return res

DFS

• consider root.right first v.s. root.left first
• avoid using left, right, i, next as variables (use start, end …)
• DFS + memorization to optimize your solutions (https://leetcode.com/problems/word-break-ii/description/) (when there are many repeated steps)

# x+y, x-y track diag
def solveNQueens(n):
    def dfs(y_list, xy_sum, xy_diff):
        if len(y_list) == n:
            res.append(y_list)
            return
        
        x = len(y_list)
        for y in range(n):
            if y not in y_list and x+y not in xy_sum and x-y not in xy_diff:
                dfs(y_list + [y], xy_sum +[x+y], xy_diff +[x-y])

    res = []
    dfs([], [], [])
    ans = [['.'*i + 'Q' + '.'*(n-i-1) for i in r] for r in res]
    return ans

BFS

# https://leetcode.com/problems/word-ladder/description/
def ladderLength(beginWord, endWord, wordList):
    wordList.add(endWord)
    queue = collections.deque([[beginWord, 1]])
    while queue:
        word, length = queue.popleft()
        if word == endWord:
            return length
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word in wordList:
                    wordList.remove(next_word)
                    queue.append([next_word, length + 1])
    return 0

Heap (Also know as priority queue)

In Python, queue.PriorityQueue is a partial wrapper around the heapq class.

In other words, a queue.PriorityQueue is actually a heapq, placed in the queue module with a couple of renamed methods to make the heapq easier to use, much like a regular queue.

Trie (prefix tree)

class TrieNode(object):
    def __init__(self):
        self.dict = {}
        self.word = ''
        
def build_trie(words):
    root = TrieNode()
    for word in words:
        p = root
        for ch in word:
            if ch not in p.dict:
                p.dict[ch] = TrieNode()
            p = p.dict[ch]
        p.word = word
    return root