This page looks best with JavaScript enabled

binary tree

node

1
2
3
4
5
6
7
8
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return f'<{self.val},{self.left},{self.right}>'

array to tree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def array_to_tree(arr):
    arr = [TreeNode(a) if a != None else None for a in arr]
    lng = len(arr)
    for i in range(lng):
        if arr[i]:
            if 2*i+2 < lng:
                arr[i].right = arr[2*i+2]
                arr[i].left = arr[2*i+1]
            elif 2*i+1 < lng:
                arr[i].left = arr[2*i+1]
    return arr[0]

3 DFS traversals

  • preorder
  • inorder
  • psotorder
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class DFS:
    def trv_preorder(self, node):
        this_method = self.get_method()
        if node:
            return [node.val] + this_method(node.left) + this_method(node.right)
        else:
            return [None]

    def trv_inorder(self, node):
        this_method = self.get_method()
        if node:
            return this_method(node.left) + [node.val] + this_method(node.right)
        else:
            return [None]

    def trv_postorder(self, node):
        this_method = self.get_method()
        if node:
            return this_method(node.left) + this_method(node.right) + [node.val]
        else:
            return [None]

    def get_method(self):
        import inspect
        level = 1
        for m in inspect.getmembers(self, predicate=inspect.ismethod):
            if m[0] == inspect.stack()[level][3]:
                return m[1]
        raise LookupError