python实现二叉树的层序、前序、中序、后序、之字形遍历

python实现二叉树的层序、前序、中序、后序遍历

1.示例

    二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

—————————————————————————
树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）：
常见的 DFS ： 先序遍历、中序遍历、后序遍历（递归法）；
常见的 BFS ： 层序遍历（即按层遍历，迭代法）。

2.层序遍历

要求：从上到下打印二叉树，同层节点按照从左往右的顺序打印，即树的广度优先搜索（BFS）。
思路：运用队列结构的思想，将同一层的节点加到队列中，每次在结果集中追加同一层节点的val。

这个版本是leetcode精选题解。使用 collections 中的双端队列 deque() ，其 popleft() 方法可达到 O(1) 时间复杂度；列表 list 的 pop(0) 方法时间复杂度为 O(N），弹出队列的首元素。
（队列特点：先进先出）

双端队列：queue = collections.deque()
		 head_node = queue.popleft()

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root: 
            return []
        res, queue = [], collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            res.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        return res

这个版本是小鸟版，使用pop()方法来弹出队列元素。

pop()方法：参见  目录8：相关知识

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        # 利用队列，层次遍历二叉树，打印
        que = []
        result = []
        if not root:
            return []
        que.append(root)
        while que:
            node = que.pop(0)
            result.append(node.val)
            if node.left:
                que.append(node.left)
            if node.right:
                que.append(node.right)
        return result

3.前序遍历

前序遍历的特点：根节点、左节点、右节点

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
	def Solution(self,root):
		result = []
		def preOrder(root):
			if not root:
				return 
			result.append(root.val)
			# 遍历左子树
			preOrder(root.left)
			# 遍历右子树
			preOrder(root.right)
		preOrder(root)
		return result

4.中序遍历

中序遍历的特点：左节点、根节点、右节点
反向中序遍历的特点：右节点、根节点、左节点

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
# 中序遍历
	def Solution(self,root):
		result = []
		def midOrder(root):
		    if not root: return
		    dfs(root.left)  # 左
		    result.append(root.val) # 根
		    dfs(root.right) # 右
		midOrder(root)
		return result

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
# 反序中序遍历
	def Solution(self,root):
		result = []
		def midOrder(root):
		    if not root: return
		    dfs(root.right)  # 左
		    result.append(root.val) # 根
		    dfs(root.left) # 右
		midOrder(root)
		return result

5.后序遍历

后序遍历的特点：左节点、右节点、根节点

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
# 后序遍历
	def Solution(self,root):
		result = []
        def postOrder(root):
            if not root:
                return 
            postOrder(root.left)
            postOrder(root.right)
            result.append(root.val)
        postOrder(root)
        print(result)
        return result

6.之字形遍历

之字形遍历，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
奇数层正序打印该层，偶数层反序打印该层，所以需要判断当前层是奇数层还是偶数层。

这个版本是leetcode精选题解。运用队列思想，偶数层则追加队列头部，奇数层则追加队列尾部。

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res, deque = [], collections.deque([root])
        while deque:
            tmp = collections.deque()
            for _ in range(len(deque)):
                node = deque.popleft()
                if len(res) % 2: tmp.appendleft(node.val) 
                # 偶数层 -> 队列头部
                else: tmp.append(node.val) 
                # 奇数层 -> 队列尾部
                if node.left: deque.append(node.left)
                if node.right: deque.append(node.right)
            res.append(list(tmp))
        return res

小鸟版

def levelOrder(self, root):
        # 之字形打印二叉树
        # 奇数层正序打印该层，偶数层反序打印该层
        result = []
        def deal(root):
            if not root:
                return []
            que = []
            que.append(root)
            while que:
                tmp = []
                for i in range(len(que)):
                    node = que.pop(0)
                    # 偶数层
                    if len(result)%2:
                        tmp.insert(0,node.val)
                    # 奇数层
                    else:
                        tmp.append(node.val)
                    if node.left:
                        que.append(node.left)
                    if node.right:
                        que.append(node.right)
                result.append(list(tmp))
        deal(root)
        return result

7.python之队列学习

可以参考博文：
队列：https://blog.csdn.net/qq_40576653/article/details/110749145

8.相关知识

博文涉及到的python相关知识可以参考以下博文：

• python中List列表函数pop():
  pop(parm)-----
  • 作用：移除列表中的一个元素（默认最后一个元素），并且返回该元素的值。
  • 参数为可选参数，参数值为列表的索引值，0<=index<=len(list)-1
• python中的队列
  • 参见 目录7.python之队列学习

9.参考链接

参考1：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solution/mian-shi-ti-32-ii-cong-shang-dao-xia-da-yin-er-c-5/
参考2：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/mian-shi-ti-32-iii-cong-shang-dao-xia-da-yin-er–3/

本文地址：https://blog.csdn.net/qq_40576653/article/details/110246785