欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

程序员文章站 2022-04-27 08:52:00
...

1. 二叉树的前序遍历

1.1 题目描述

难度:中等
LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

1.2 题目分析

这道题目是二叉树相关问题的基础类问题,利用递归是比较容易想到的方法,但是进阶问题要求用迭代算法来完成,这个需要好好想一下。但是关于二叉树的前序,中序,后序遍历都有一个统一的模板可以套用,我们来看看这个模板是什么:

"""
二叉树遍历模板
采用栈的方法
"""
stack = []
cur = root
while stack or cur:
    if cur:
    	pass
    else:
    	pass

二叉树的前序,中序,后序遍历都可以利用上述的栈的模板实现,只需要根据情况修改代码中的pass段即可。二叉树的前序遍历的顺序是根节点->左子树->右子树。我们来看一下二叉树的前序遍历是怎么实现的。

1.3 Python实现
  • 递归
    先用递归的方法实现一下:
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

运行结果为:
LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

  • 迭代(栈)
    利用上述模板来实现:
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []
        res = []
        cur = root
        while stack or cur:
            if cur:
                stack.append(cur)
                res.append(cur.val)
                cur = cur.left
            else:
                cur = stack.pop()
                cur = cur.right
        return res

运行结果为:
LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

2. 二叉树的中序遍历

2.1 题目描述

难度:中等
LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

2.2 题目分析

中序遍历与前序遍历相似,遍历顺序为左子树->根节点->右子树,实现方式有递归和迭代两种,迭代是利用1.2节中的模板来实现的。

2.3 Python实现
  • 递归实现
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

输出结果为:
LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

  • 迭代实现(栈)
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        cur = root
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                res.append(cur.val)
                cur = cur.right
        return res

输出结果为:
LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

3. 二叉树的后序遍历

2.1 题目描述

难度:困难
LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

2.2 题目分析

后序遍历的顺序是 左子树->右子树->根节点,后序序遍历与前序、中序遍历相似,实现方式有递归和迭代两种,迭代是利用1.2节中的模板来实现的。

2.3 Python实现
  • 递归实现
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

运行结果为:
LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

  • 迭代实现(栈)
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        cur = root
        temp = None
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack[-1]
                if(cur.right is None or cur.right == temp):
                    res.append(cur.val)
                    temp = cur
                    stack.pop()
                    cur = None
                else:
                    cur = cur.right

        return res

运行结果为:
LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

4. 二叉树的层序遍历

2.1 题目描述

难度:中等
LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

2.2 题目分析

层序遍历的遍历顺序是:第一层:根节点,第二层:左节点,右节点,第三层…,输出是二维的列表形式。与前三题不同,层序遍历不能依靠栈的结构实现,而要依靠队列进行实现。步骤如下:

  • 将根节点放入队列
  • 将队列中的节点取出,并将其值加入到输出的结果中,并把该节点左右子节点放入队列
  • 以队列的长度为循环次数,依次取出队列的列首值,并将节点的值加入到输出结果中,并同时将节点的左右子节点放入队列
  • 重复第三个步骤,直到队列为空
2.3 Python实现

代码如下:

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

# 队列
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res = []
        queue = [root]
        temp = []
        while queue:
            lens = len(queue)
            temp = []
            while lens:
                cur = queue[0]
                del queue[0]
                temp.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
                lens -= 1
            res.append(temp)
        return res

输出结果为:
LeetCode--144,94,145,102 二叉树的前序、中序、后序、层序遍历(递归,迭代,栈,队列)

相关标签: # •Tree