@二叉树总结
从今天开始记录每天的学习生活了,之前不怎么写博客,对Markdown语法虽然学了一些但是依旧不是很熟悉,力扣的题目都是通过pycharm来记录的,以后通过这种形式,记录一下,记录各种学习,做算法题,做项目的日常
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
提示:这里可以添加本文要记录的大概内容:
例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器学习,本文就介绍了机器学习的基础内容。
提示:以下是本篇文章正文内容,下面案例可供参考
代码如下(示例):
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right
递归方式好写,但是迭代方式可以参考以下思路,这是目前我认为比较好理解和记住的方式。
思路:
代码如下(示例):
# 递归方式 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
中序后序都是类似的,这里就不重复介绍思路了
代码如下(示例)
# 递归方式 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
代码如下(示例)
# 递归思路 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
关于二叉树的遍历,今天就到这里,下次继续分享