非递归遍历二叉树的方法

发表于 | 分类于 | |

前言

统一的简洁的二叉树非递归遍历写法

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def preOrder(root,path):
    s = []
    if not root:
        return s
    s.push([root,False])
    while not s:
        node, visited = s[-1]
        s.pop()
        if not node:
            continue
        if visited:
            path.append(node)
        else:
            s.append([node.right,False])
            s.append([node.left,False])
            s.append([node,True])
    return path

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def inOrder(root,path):
    s = []
    if not root:
        return s
    s.push([root,False])
    while not s:
        node, visited = s[-1]
        s.pop()
        if not node:
            continue
        if visited:
            path.append(node)
        else:
            s.append([node.right,False])
            s.append([node,True])
            s.append([node.left,False])
    return path

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def postOrder(root,path):
    s = []
    if not root:
        return s
    s.push([root,False])
    while not s:
        node, visited = s[-1]
        s.pop()
        if not node:
            continue
        if visited:
            path.append(node)
        else:
            s.append([node,True])
            s.append([node.right,False])
            s.append([node.left,False])
    return path