Algorithms

Names

Ref

非递归的二叉树遍历

递归实现

# pre-order traversal
def preorder(Node root):
    if not root:
        pass
    else:
        preorder(root.left)
        print root.val
        preorder(root.right)

# in-order traversal
def inorder(Node root):
    if not root:
        pass
    else:
        preorder(root.left)
        print root.val
        preorder(root.right)

# post-order traversal
def postorder(Node root):
    if not root:
        pass
    else:
        preorder(root.left)
        preorder(root.right)
        print root.val

非递归实现 using stack

# preorder
def preorder2(Node root):
    s = list()
    p = root
    while p or s:
        while p:
            s.append(p)
            print p.val // access
            p = p.left()
        if s:
            p = s.pop()
            p = p.right



# inorder
def inorder2(Node root):
    s = list()
    p = root
    while p or s:
        while p:
            s.append(p)
            p = p.left
        if s:
            p = s.pop()
            print p.val // access
            p = p.right



# postorder (2 thoughts)

## reverse a right-tree-first preorder
def postorder2(Node root):
    ans = []
    s = list()
    p = root
    while p or s:
        while p:
            s.append(p)
            ans.append(p.val) // access
            p = p.right
        if s:
            p = s.pop()
            p = p.left

    ans = ans[::-1] // reverse
    return ans


# visited flag
# applicable for all 3 traversal methods
def postorder2(Node root):
    ans, stack = [], [(root, False)]
    while stack:
        node, visited = stack.pop()
        if node:
            if visited:
                # add to result if visited
                ans.append(node.val)
            else:
                # pre-order
                stack.append((node.right, False))
                stack.append((node.left, False))
                stack.append((node, True))
                # in-order
                stack.append((node.right, False))
                stack.append((node, True))
                stack.append((node.left, False))
                # post-order
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))
    return ans

层次遍历 using queue

from collections import deque
def levelorder(root):
    if not root:
        return
    ans = []
    s = list(root)
    p = root

    while s:
        p = s.popleft()
        ans.append(p.val)
        if p.left:
            s.append(p.left)
        if p.right:
            s.append(p.right)   
    return ans

Ref