力扣(LeetCode)之二叉树遍历

二叉树的遍历主要有三种方法：递归遍历、迭代遍历、morris遍历 。
三种顺序：前序遍历、中序遍历、后序遍历、层序遍历、

• 前序遍历：根 - 左 - 右
• 中序遍历：左 - 根 - 右
• 后序遍历：左 - 右 - 根
• 层序遍历：一层一层遍历，从上往下，从左往右
• 递归遍历：使用递归方法遍历
• 迭代遍历：使用迭代方法实现递归函数，与递归函数等价

（1）递归实现二叉树遍历

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.deep = 0

# 二叉树1
# node7 = TreeNode(7)
# node15 = TreeNode(15)
# node9 = TreeNode(9)
# node20 = TreeNode(20, node15, node7)
# node3 = TreeNode(3, node9, node20)

# 二叉树2
# node6 = TreeNode(6)
# node5 = TreeNode(5,None,node6)
# node4 = TreeNode(4,None,node5)
# node3 = TreeNode(3,None, node4)
# node2 = TreeNode(2,None,node3)

# 二叉树3
node7 = TreeNode(7)
node6 = TreeNode(6)
node5 = TreeNode(5,node6, node7)
node4 = TreeNode(4)
node3 = TreeNode(3)
node2 = TreeNode(2,node4, node5)
node1 = TreeNode(1, node2, node3)

root = node1

# 递归实现前序遍历
def recurrent1(root):
    if root == None: return 
    print(root.val) # 第一次成为栈顶元素的时候进行打印
    recurrent1(root.left)
    recurrent1(root.right)

# 递归实现中序遍历
def recurrent2(root):
    if root == None: return 
    recurrent2(root.left)
    print(root.val) # 第二次成为栈顶元素的时候进行打印
    recurrent2(root.right)

# 递归实现后序遍历
def recurrent3(root):
    if root == None: return
        # print(root) 
    recurrent3(root.left)
    recurrent3(root.right)
    print(root.val)

# 递归实现层序遍历
def layer_order(root):
    arr = []
    recurrent3(root, 1, arr)
    for i in arr:
        if i != None: print(i)

def recurrent3(root, index, arr):
    # 我们知道二叉树每一层，节点数量最多为：1、2、4、8、16
    # 其实如果我们使用一个数组存储一棵二叉树的话，他们都是有自己独一无二的下标的
    # 假设第一个节点的下标为1，那么它的左子节点的下表是2*1，右子节点的下表是2*1+1
    # 假设第n个节点的下标为i，那么它的左子节点的下标就是2*i,右子节点的下标就是2*i+1
    if root == None: return
    # 这里是为了防止数组越界的问题
    l = len(arr)
    if l<=index:
        for _ in range(index-l+1): 
            arr.append(None)
    arr[index] = root.val
    recurrent3(root.left, 2*index, arr)
    recurrent3(root.right, 2*index+1, arr)

layer_order(root) 

（2）迭代实现二叉树遍历

from collections import deque
import queue

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.deep = 0

# 二叉树1
# node7 = TreeNode(7)
# node15 = TreeNode(15)
# node9 = TreeNode(9)
# node20 = TreeNode(20, node15, node7)
# node3 = TreeNode(3, node9, node20)

# 二叉树2
# node6 = TreeNode(6)
# node5 = TreeNode(5,None,node6)
# node4 = TreeNode(4,None,node5)
# node3 = TreeNode(3,None, node4)
# node2 = TreeNode(2,None,node3)

# 二叉树3
node7 = TreeNode(7)
node6 = TreeNode(6)
node5 = TreeNode(5, node6, node7)
node4 = TreeNode(4)
node3 = TreeNode(3)
node2 = TreeNode(2, node4, node5)
node1 = TreeNode(1, node2, node3)

root = node1


# 使用迭代的方法实现前序遍历
def Fun1(root):
    if root != None:
         stack = deque()
         stack.append(root)
    while len(stack) > 0:
        root = stack.pop()
        if root != None:
            print(root.val)
            stack.append(root.right)
            stack.append(root.left)

# 使用迭代的方法实现中序遍历
def Fun2(root):
    stack = deque()
    while len(stack)>0 or root != None:
        if root != None:
            stack.append(root)
            root = root.left
        else:
            root = stack.pop()
            print(root.val)
            root = root.right 
        
# 使用迭代的方法实现后序遍历
def Fun3(root):
    stack = deque() 
    prev = None
    while len(stack)>0 or root != None:
        while root != None:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if root.right == None or root.right == prev:
            print(root.val)
            prev = root
            root = None
        else:
            stack.append(root)
            root = root.right

# 使用迭代的方法实现层序遍历
def Fun4(root):
    q = queue.Queue()
    q.put(root)
    while not q.empty():
        node = q.get()
        if node != None: print(node.val)
        if node.left != None: q.put(node.left)
        if node.right != None: q.put(node.right)

Fun4(root)

（3）使用morris实现二叉树遍历

# 首先需要维护中序线索二叉树
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        self.deep = 0

# 二叉树1
# node7 = TreeNode(7)
# node15 = TreeNode(15)
# node9 = TreeNode(9)
# node20 = TreeNode(20, node15, node7)
# node3 = TreeNode(3, node9, node20)

# 二叉树2
# node6 = TreeNode(6)
# node5 = TreeNode(5,None,node6)
# node4 = TreeNode(4,None,node5)
# node3 = TreeNode(3,None, node4)
# node2 = TreeNode(2,None,node3)

# 二叉树3
node7 = TreeNode(7)
node6 = TreeNode(6)
node5 = TreeNode(5, node6, node7)
node4 = TreeNode(4)
node3 = TreeNode(3)
node2 = TreeNode(2, node4, node5)
node1 = TreeNode(1, node2, node3)

root = node1

# morris节点实现前序遍历
def fun1(cur):
    if cur == None: return 
    most_right = None 
    while cur != None:
        most_right = cur.left
        if most_right != None: # 先找左子树
            while most_right.right != None and most_right.right != cur: # 找左子树的最右边的节点
                most_right = most_right.right 
            if most_right.right == None:
                most_right.right = cur # 将叶子节点的指针进行维护,建立线索指针
                print(cur.val)
                cur = cur.left 
                continue
            if most_right.right == cur:
                most_right.right = None # 删除线索指针
        else: # 找右子树 
            print(cur.val)
        cur = cur.right   

# morris节点实现中序遍历
def fun2(cur):
    if cur == None: return 
    most_right = None 
    while cur != None:
        most_right = cur.left
        if most_right != None: # 先找左子树
            while most_right.right != None and most_right.right != cur: # 找左子树的最右边的节点
                most_right = most_right.right 
            if most_right.right == None:
                most_right.right = cur # 将叶子节点的指针进行维护,建立线索指针
                cur = cur.left 
                continue
            if most_right.right == cur:
                most_right.right = None # 删除线索指针
        # else: # 找右子树 
        #     print(cur.val)
        print(cur.val)
        cur = cur.right 

# morris节点实现后序遍历
def fun3(cur):
    if cur == None: return 
    root = cur
    most_right = None 
    while cur != None:
        most_right = cur.left
        if most_right != None: # 先找左子树
            while most_right.right != None and most_right.right != cur: # 找左子树的最右边的节点
                most_right = most_right.right 
            if most_right.right == None:
                most_right.right = cur # 将叶子节点的指针进行维护,建立线索指针
                cur = cur.left 
                continue
            if most_right.right == cur:
                most_right.right = None # 删除线索指针
                printf(cur.left)
        cur = cur.right  
    printf(root)

def printf(head):
    # 首先将链表进行反转
    tail = reverse(head)
    while tail != None:
        print(tail.val)
        tail = tail.right
    reverse(tail)

def reverse(head):
    next = None 
    prev = None
    cur = head 

    while cur != None:
        next = cur.right 
        cur.right = prev
        prev = cur 
        cur = next
    return prev

fun3(root)