四川住房建设厅网站首页,中国最新战备状态,凡客优品家居,太原关键词排名推广二叉树的遍历详解#xff1a;前、中、后、层次遍历(Python实现)二叉树是一种常见的数据结构#xff0c;而它的常见遍历方法有前序遍历、中序遍历、后续遍历、层次遍历——掌握这几种遍历方法是很有必要的。假设我们二叉树节点的定义如下——# Definition for a binary tree n…二叉树的遍历详解前、中、后、层次遍历(Python实现)二叉树是一种常见的数据结构而它的常见遍历方法有前序遍历、中序遍历、后续遍历、层次遍历——掌握这几种遍历方法是很有必要的。假设我们二叉树节点的定义如下——# Definition for a binary tree node.class TreeNode:def __init__(self, x):self.val xself.left Noneself.right None前序遍历1. 深度优先遍历(递归实现)我们先看前序遍历二叉树的过程——访问根结点前序遍历左子树前序遍历右子树很容易就可以看出这个过程是递归的所以可以很方便使用递归实现前序遍历。def preorderTraversal(root: TreeNode) - List[int]:res []dfs(root, res)return resdef dfs(root: TreeNode, res: List[int]) - None:if not root: returnres.append(root.val)dfs(root.left, res)dfs(root.right, res)python 特色的二叉树前序遍历递归实现def preorderTraversal(root: TreeNode) - List[int]:if not root: return []return [root.val] preorderTraversal(root.left) preorderTraversal(root.right)2.深度优先遍历(迭代实现)由于递归是隐式的使用了栈(函数栈)所以也可以直接使用栈来实现递归。def preorderTraversal(root: TreeNode) - List[int]:if root is None: return []res, stack [], [root]while stack:node stack.pop()if not node: continueres.append(node.val)if node.right:stack.append(node.right)if node.left:stack.append(node.left)return res3.(颜色)标记法核心思想如下:使用标记记录节点的状态比如使用 flag当 flag True 表示该节点未被访问如果遇到未被访问的节点则令 flag False依次将右节点、左节点、自身入栈如果遇到已访问过的节点则将节点的值输出而只需要调整左右节点的入栈顺序就可以变为中序遍历和后序遍历了。def preorderTraversal(root: TreeNode) - List[int]:res, stack [], [(root, True)]while stack:node, flag stack.pop()if not node: continueif flag:stack.append((node.right, True))stack.append((node.left, True))stack.append((node, False))else:res.append(node.val)return res中序遍历1.深度优先遍历(递归实现)中序遍历二叉树的过程——中序遍历左子树访问根结点中序遍历右子树因此很容易使用递归实现中序遍历。def inorderTraversal(root: TreeNode) - List[int]:res []dfs(root, res)return resdef dfs(root: TreeNode, res: List[int]) - None:if not root: returndfs(root.left, res)res.append(root.val)dfs(root.right, res)python 特色的二叉树中序遍历递归实现def inorderTraversal(root: TreeNode) - List[int]:if not root: return []return inorderTraversal(root.left) [root.val] inorderTraversal(root.right)2.深度优先遍历(迭代实现)由于递归是隐式的使用了栈(函数栈)所以也可以直接使用栈来实现递归。def inorderTraversal(root: TreeNode) - List[int]:res, stack, cur [], [], rootwhile stack or cur:while cur:stack.append(cur)cur cur.leftcur stack.pop()res.append(cur.val)cur cur.rightreturn res3.(颜色)标记法核心思想如下:使用标记记录节点的状态比如使用 flag当 flag True 表示该节点未被访问如果遇到未被访问的节点则令 flag False依次将右节点、自身、左节点入栈如果遇到已访问过的节点则将节点的值输出与前序遍历相比仅改变了左节点和当前节点的入栈顺序。def inorderTraversal(root: TreeNode) - List[int]:res, stack [], [(root, True)]while stack:node, flag stack.pop()if not node: continueif flag:stack.append((node.right, True))stack.append((node, False))stack.append((node.left, True))else:res.append(node.val)return res后序遍历1.深度优先遍历(递归实现)后序遍历二叉树的过程——后序遍历左子树后序遍历右子树访问根结点因此很容易使用递归实现后序遍历。def postorderTraversal(root: TreeNode) - List[int]:res []dfs(root, res)return resdef dfs(root: TreeNode, res: List[int]) - None:if not root: returndfs(root.left, res)dfs(root.right, res)res.append(root.val)python 特色的二叉树后序遍历递归实现def postorderTraversal(root: TreeNode) - List[int]:if not root: return []return postorderTraversal(root.left) postorderTraversal(root.right) [root.val]2.深度优先遍历(迭代实现)def postorderTraversal(root: TreeNode) - List[int]:if root is None: return []res, stack [], [root]while stack:node stack.pop()if not node: continueres.append(node.val)if node.left:stack.append(node.left)if node.right:stack.append(node.right)return res[::-1]3.(颜色)标记法核心思想如下:使用标记记录节点的状态比如使用 flag当 flag True 表示该节点未被访问如果遇到未被访问的节点则令 flag False依次将自身、右节点、左节点入栈如果遇到已访问过的节点则将节点的值输出def postorderTraversal(root: TreeNode) - List[int]:res, stack [], [(root, True)]while stack:node, flag stack.pop()if not node: continueif flag:stack.append((node, False))stack.append((node.right, True))stack.append((node.left, True))else:res.append(node.val)return res层次遍历1.深度优先遍历(递归实现)层次遍历相对于前中后序遍历而言加多节点所在二叉树层数的信息。所以只需要添加一个变量 level 记录层数即可。def levelOrder(root: TreeNode) - List[List[int]]:res []dfs(root, 0)return resdef dfs(root: TreeNode, level: int) - None:if not root: returnif len(res) level:res.append([])res[level].append(root.val)dfs(root.left, level1)dfs(root.right, level1)2.深度优先遍历(迭代实现)由于递归是隐式的使用了栈(函数栈)所以也可以直接使用栈来实现递归。我们不妨使用一个二元组 (node, level) 来表示状态。def levelOrder(root: TreeNode) - List[int]:res, stack [], [(root, 0)]while stack:node, level stack.pop()if not node: continueif len(res) level:res.append([])res[level].append(node.val)if node.right:stack.append(node.right)if node.left:stack.append(node.left)return res3.(颜色)标记法相对于前序遍历的标记法层次遍历的标记法也仅仅添加了节点层数(level)的变量。def levelOrder(root: TreeNode) - List[int]:res, stack [], [(root, True, 0)]while stack:node, flag, level stack.pop()if not node: continueif flag:stack.append((node.right, True, level1))stack.append((node.left, True, level1))stack.append((node, False))else:if len(res) level:res.append([])res[level].append(node.val)return res4.广度优先遍历(队列实现)因为层次遍历是逐层遍历的所以可以使用广度优先遍历。使用队列实现广度优先遍历具体实现方法如下——首先根节点入队当队列不为空的时候当前队列长度 si (当前队列长度即为当前层的节点数)依次从队列中取出 si 元素将其左右节点入队进行下一次迭代def levelOrder(root: TreeNode) - List[int]:if not root: return []res, queue [], [root]while queue:level_node []for _ in range(len(queue)):node queue.pop(0)level_node.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(level_node)return res
