python 三序遍历的迭代和递归实现_python3 层序遍历

 1、一些关于生成和遍历打印链表节点的测试代码

class LinkNode():
    # 单链表的节点
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
 
def generate_link(arr):
    # input：数组
    # output：链表首节点
    res = pre = LinkNode()
    for i in arr:
        tmp = LinkNode(val=i)
        pre.next = tmp
        pre = pre.next
    return res.next
 
def look_link(root):
    # 遍历打印链表
    while root:
        # print(root.val)
        root = root.next
    print("look_link finish")
        
look_link(generate_link(list(range(10))))
 
 
class BinaryTreeNode():
    # 二叉树节点
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def generate_tree(arr):
    # input：数组
    # output：二叉树首节点
    if not arr:
        return
    # 原数组上修改
    arr[0] = BinaryTreeNode(arr[0])
    for i in range(1, len(arr)):
        # print('----arr[i]', i, arr[i])
        if arr[i] is not None:
            arr[i] = BinaryTreeNode(arr[i])
        # print('\t', i & 1, i // 2, arr[i])
        # 利用二叉树的节点位置和其左子树右子树位置的关系
        # 节点A的位置是n，则左节点是2n，右节点是2n + 1
        if i & 1 == 1:
            # 奇数：是左节点
            arr[(i -1) // 2].left = arr[i]
        else:
            # 偶数：是右节点
            arr[(i -1) // 2].right = arr[i]
    # print('---generate_tree-', arr)
    # for i in arr:
    #     print(i.val)
    return arr[0]
 
def look_tree(root):
    # 遍历打印二叉树
    if not root:
        return
    print("look_tree start")
    # 层序遍历
    stack = [root]
    while stack:
        tmp = stack.pop(0)
        print("\tlook: ", tmp.val)
 
        if tmp.val is None:
            continue
        if tmp.left:
            stack.append(tmp.left)
        if tmp.right:
            stack.append(tmp.right)
    print("look_tree finish")
        
# look_tree(generate_tree([1,2,5,3,4,None,6]))
# 保证二叉树的左边 < 中间< 右边

层序遍历

# 层序遍历
r = generate_tree([1,2,5,3,4,None,6])
 
# levelOrder(r)
# 迭代（一维）
def one_level_diedai(root):
    res = []
    stack = [root]
    while stack:
        node = stack.pop(0)
        res.append(node.val)
        if node.left:
       		stack.append(node.left)
 
        if node.right:
        	stack.append(node.right)
    return res
res = one_level_diedai(r)
print("----one_level_diedai ", res)
 
 
# 迭代 （二维数组）
def levelOrder(root):
    if not root:
        return
    print("levelOrder start")
 
    res = []
    stack = [root]
    while stack:
        tmp_list = []
        length = len(stack)
        for i in range(length): # 每次弹出当层的次数
            tmp = stack.pop(0) # 先进先出
            print("\tlook: ", tmp.val)
 
            if tmp.val is None:
                continue
            tmp_list.append(tmp.val)
 
            if tmp.left:
                stack.append(tmp.left)
            if tmp.right:
                stack.append(tmp.right)
        res.append(tmp_list)
    print("levelOrder finish", res)
    return res
 

前序遍历

# 迭代
def first_order_diedai(root):
    res = []
    stack = []
    while stack or root:
        while root:
            stack.append(root)
            res.append(root.val) # 注意
            root = root.left
 
        root = stack.pop()
        root = root.right
    return res
 
# 递归
def first_order_digui(root):
    if root:
        res.append(root.val)
        first_order_digui(root.left)
        first_order_digui(root.right)
 
 
r = generate_tree([1,2,5,3,4,None,6])
 
# res = []
# firstOrder_digui(r)
# print("----res ", res)
res = first_order_diedai(r)
print("----first_order_diedai ", res)

中序遍历

# 中序遍历
def mid_bianli(root):
    res = []
    stack = []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
 
        root = stack.pop()
        res.append(root.val) # 注意
        root = root.right
    
    return res
 
# 递归
def mid_bianli_digui(root):
    if root:
        mid_bianli_digui(root.left)
        res.append(root.val) # 注意
        mid_bianli_digui(root.right)
 
res = mid_bianli(r) 
print("----mid_bianli ", res)

后序遍历

# 迭代
# 左右中：即中右左的翻转
def last_bianli(root):
    res = []
    stack = []
    while stack or root:
        while root:
            stack.append(root)
            res.append(root.val) # 先序的倒序
            root = root.right # 从右子树开始
 
        root = stack.pop()
        root = root.left
 
    return res[::-1] # 倒序
 
# 递归
def first_order_digui(root):
    if root:
        first_order_digui(root.left)
        first_order_digui(root.right)
        res.append(root.val)
 
res = last_bianli(r)
print("----last_bianli ", res)
 
# res = []
# first_order_digui(r)
# print("----first_order_digui ", res)

链表展开

def flatten(root):
    # 把每个子树合成链表
    # 把左子树的节点一次插入到根节点和右节点中间
    if not root:
        # 空节点
        return
    print("flatten", root, root.val)
 
    # 只有右节点时不用处理
    flatten(root.left)
    flatten(root.right)
    if root.left:
        print('0----left', root.left, root.left.val)
        # 把 左节点插入到根节点和右节点中间
        tmp = root.right # 暂存右节点
        root.right = root.left # 把 右节点指向原先的左节点
        tmp2 = root.right
        while tmp2 and tmp2.right:
            tmp2 = tmp2.right
        tmp2.right = tmp # 找到左子树的最右节点，然后指向 根节点的右节点
        root.left = None # 把左节点置空
        print('\t', root.left, root.right.val)
 
r = generate_tree([1,2,5,3,4,None,6])
look_tree(r)
flatten(r)
look_tree(r) # 1,2,3,4,5,6