本文主要是介绍2021-06-26力扣算法题总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

@二叉树总结

二叉树阶段性总结

从今天开始记录每天的学习生活了，之前不怎么写博客，对Markdown语法虽然学了一些但是依旧不是很熟悉，力扣的题目都是通过pycharm来记录的，以后通过这种形式，记录一下，记录各种学习，做算法题，做项目的日常

二叉树的遍历

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 二叉树阶段性总结
• • 二叉树的遍历
• 前言
• 一、基于深度优先遍历方式的三种遍历
• • 二叉树的定义：
  • 1.前序遍历（根->左->右）
  • 2.中序遍历（左->根->右）
  • 3.后序遍历
• 二、基于广度优先遍历的三种方式
• 总结

前言

提示：这里可以添加本文要记录的大概内容：
例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。

提示：以下是本篇文章正文内容，下面案例可供参考

一、基于深度优先遍历方式的三种遍历

二叉树的定义：

代码如下（示例）：

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

1.前序遍历（根->左->右）

递归方式好写，但是迭代方式可以参考以下思路，这是目前我认为比较好理解和记住的方式。

思路：

• 利用栈后进先出的特性
• 入栈顺序是左右根
• 出栈顺序就是根左右

代码如下（示例）：

# 递归方式
	def preorderTraversal1(self, root: TreeNode) -> List[int]:
		# 基于根左右的方式就行递归添加节点值
		def dfs(root: TreeNode): 
			if not root:
				return []
			res.append(root.val) 
			dfs(root.left)
			dfs(root.right)
		res = []
		dfs(root)
		return res
# 迭代方式
    def preorderTraversal2(self, root: TreeNode) -> List[int]:
        if not root: 
            return []
		# 这里使用到了栈，利用栈后进先出的特性
        res, stack = [], [root]
        while stack:
            node = stack.pop()
            if node and type(node) == int: # 找到根的值添加进去
                res.append(node)
                continue
            # 注意这里添加的顺序是左右根
            if node: # 这里只要节点非空就添加其他信息
                stack.append(node.right) # 添加左孩子
                stack.append(node.left)  # 添加右孩子
                stack.append(node.val)   # 添加根的值
        return res

2.中序遍历（左->根->右）

中序后序都是类似的，这里就不重复介绍思路了
代码如下（示例）

# 递归方式
	def inorderTraversal1(self, root: TreeNode) -> List[int]:
		def dfs(root: TreeNode): 
			if not root:
				return []
			
			dfs(root.left)
			res.append(root.val) 
			dfs(root.right)
		res = []
		dfs(root)
		return res
# 迭代方式
    def inorderTraversal2(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res, stack = [], [root]
        while stack:
            node = stack.pop()
            if node and type(node) == int:
                res.append(node)
                continue
            if node:
                stack.append(node.right)
                stack.append(node.val)
                stack.append(node.left)
        return res

3.后序遍历

代码如下（示例）

# 递归思路
	def postorderTraversal1(self, root: TreeNode) -> List[int]:
		def dfs(root: TreeNode): 
			if not root:
				return []
			
			dfs(root.left)
			res.append(root.val) 
			dfs(root.right)
		res = []
		dfs(root)
		return res
#迭代思路
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        res, stack = [], [root]
        while stack:
            node = stack.pop()
            if node and type(node) == int:
                res.append(node)
                continue
            if node:
                stack.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
        return res

以上就是基于深度优先遍历的三种二叉树的比那里方式，后序我还会继续总结其他有关二叉树的知识

二、基于广度优先遍历的三种方式

代码如下（示例）：

from collections import deque
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        queue = deque([root])
        res = []
        while queue:
            res1 = []
            for i in range(len(queue)):
                cur = queue.popleft()
                res1.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            res.append(res1)
        return res

总结

关于二叉树的遍历，今天就到这里，下次继续分享

这篇关于2021-06-26力扣算法题总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！