Skip to content

Instantly share code, notes, and snippets.

@kk-r

kk-r/tree_traversal_template.py

Forked from RuolinZheng08/tree_traversal_template.py
Created August 11, 2021 12:33
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kk-r/8eeb68cda52cbbeb6d260cac3cecfff5 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kk-r/8eeb68cda52cbbeb6d260cac3cecfff5 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @RuolinZheng08 RuolinZheng08 created this gist Nov 20, 2020.
    63 changes: 63 additions & 0 deletions tree_traversal_template.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,63 @@
    # DFS
    def preorder(self, root):
    if not root:
    return []
    ret = []
    stack = [root]
    while stack:
    node = stack.pop()
    ret.append(node.val)
    if node.right:
    stack.append(node.right)
    if node.left:
    stack.append(node.left)
    return ret

    def postorder(self, root):
    if not root:
    return []
    from collections import deque
    ret = deque()
    stack = [root]
    while stack:
    node = stack.pop()
    ret.appendleft(node.val)
    if node.left:
    stack.append(node.left)
    if node.right:
    stack.append(node.right)
    return ret

    def inorder(self, root):
    if not root:
    return []
    ret = []
    stack = []
    while root is not None or stack:
    while root is not None:
    stack.append(root)
    root = root.left
    root = stack.pop()
    ret.append(root.val)
    root = root.right
    return ret

    # BFS
    def levelorder(self, root):
    if not root:
    return []
    ret = []
    from collections import deque
    queue = deque([root])
    while queue:
    ret_row = []
    # fixed size for current level
    for _ in range(len(queue)):
    node = queue.popleft()
    ret_row.append(node.val)
    if node.left:
    queue.append(node.left)
    if node.right:
    queue.append(node.right)
    ret.append(ret_row)
    return ret