Tree traversal

树的遍历

前序（preorder），我们访问该几点，然后访问该节点的左子树和右子树；
中序（inoder），我们访问该节点的左子树，然后访问该节点，再访问该节点的右子树；
后序（postorder），我们访问该节点的左子树和右子树，再访问该节点。

递归遍历

preorder.c

void traverse(link h, void(*visit)(link))
{
    if(h == NULL) return;
    (*visit) (h);
    traverse(h->l, visit);
    traverse(h->r, visit);
}

非递归遍历

所有的递归都可以用迭代来实现么？

preorder.c

void traverse(link h, void(*visit)(link))
{
    STACKinit(max);
    STACKpush(h);
    while(!STACKempty())
    {
        (*visit)(h = STACKpop());
        if (h->r != NULL) STACKpush(h->r);
        if (h->l != NULL) STACKpush(h->l);
    }
}

使用True OR False来标记是否访问过

postorder.py

def postorder(root):
    ret, stack = [], [(root, False)]
    while stack:
        node, is_visited = stack.pop()
        if node:
            if is_visited:
                ret.append(node.val)
            else:
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))
    return ret

Leetcode相关练习题

Reference

Algorithm IN C