赤峰做网站开发,负责公司网站的更新和维护,餐饮管理系统有哪些,推广平台有哪些适用于广告关于二叉树的前序遍历#xff08;preoder#xff09;、中序遍历#xff08;inorder#xff09;和后序遍历#xff08;postorder#xff09;#xff0c;实际上只需要记住#xff1a;左子节点一定在右子节点的左边#xff08;左右#xff09;#xff0c;所谓前中后序遍…关于二叉树的前序遍历preoder、中序遍历inorder和后序遍历postorder实际上只需要记住左子节点一定在右子节点的左边左右所谓前中后序遍历就是根节点的位置不同前序是根左右中序是左根右后序是左右根。
python代码实现先定义树节点的类如下
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right right然后是前中后序的递归法实现非常直观 # 前序遍历def preorderTraversal(self, root: TreeNode) - List[int]:def preorder(root: TreeNode):if not root:returnans.append(root.val) # 根左右preorder(root.left)preorder(root.right)ans list()preorder(root)return ans# 中序遍历def inorderTraversal(self, root: TreeNode) - List[int]:def inorder(root: TreeNode):if not root:returninorder(root.left) # 左根右ans.append(root.val)inorder(root.right)ans list()inorder(root)return ans# 后序遍历def postorderTraversal(self, root: TreeNode) - List[int]:def postorder(root: TreeNode):if not root:returnpostorder(root.left) # 左右根postorder(root.right)ans.append(root.val)ans list()postorder(root)return ans可以看到实际上前中后序的递归法实现区别仅仅在于访问左右子节点和将根节点加入结果数组的顺序不同。
迭代法实现复杂一点一般是使用一个栈如下 # 前序遍历def preorderTraversal(self, root: Optional[TreeNode]) - List[int]:ans []if not root:return ansstack []stack.append(root)while stack:node stack.pop()if node:if node.right: # 右stack.append(node.right)if node.left: # 左stack.append(node.left)stack.append(node) # 根stack.append(None)else:node stack.pop()ans.append(node.val)return ans# 中序遍历def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:ans []if not root:return ansstack []stack.append(root)while stack:node stack.pop()if node:if node.right: # 右stack.append(node.right)stack.append(node) # 根stack.append(None)if node.left: # 左stack.append(node.left)else:node stack.pop()ans.append(node.val)return ans# 后序遍历def postorderTraversal(self, root: Optional[TreeNode]) - List[int]:ans []if not root:return ansstack []stack.append(root)while stack:node stack.pop()if node:stack.append(node) # 根stack.append(None)if node.right: # 右stack.append(node.right)if node.left: # 左stack.append(node.left)else:node stack.pop()ans.append(node.val)return ans可以看到前中后序遍历的迭代写法是统一的唯一区别就是中间的代码只需要记住从下往上是根左右前序、左根右中序、左右根后序即可。
对于N叉数思路和二叉树是比较相似的。先看下N叉数的树节点定义
# Definition for a Node.
class Node:def __init__(self, valNone, childrenNone):self.val valself.children children589. N 叉树的前序遍历
class Solution:def preorder(self, root: Node) - List[int]:def preorderTravel(root: Node):if not root:returnans.append(root.val)for child in root.children:preorderTravel(child)ans list()preorderTravel(root)return ans递归写法区别只是用for循环遍历所有子节点而不是只遍历左右子节点。
class Solution:def preorder(self, root: Node) - List[int]:if not root:return []stack [root,]output [] while stack:root stack.pop()output.append(root.val)stack.extend(root.children[::-1])return output迭代写法这里注意入栈的是root.children[::-1]这样出栈时才是从左子树到右子树正确的顺序。
590. N 叉树的后序遍历
class Solution:def postorder(self, root: Node) - List[int]:def postorderTravel(root: Node):if not root:returnfor child in root.children:postorderTravel(child)ans.append(root.val)ans list()postorderTravel(root)return ans递归写法相比前序遍历只是交换了一下位置而N叉数没有中序遍历。
class Solution:def postorder(self, root: Node) - List[int]:if not root:return []stack [root,]output []while stack:root stack.pop()if root:output.append(root.val)for child in root.children:stack.append(child)return output[::-1]迭代写法。
559. N 叉树的最大深度
class Solution:def maxDepth(self, root: Node) - int:if not root:return 0elif root.children []:return 1else:temp list()for child in root.children:temp.append(self.maxDepth(child))return max(temp) 1递归与二叉树的最大深度类似注意要判断 root.children [] 时深度为1。
还有一种遍历二叉树的方法可以将空间复杂度降至O(1)名为Morris遍历对其解释地最好的我觉得是这篇文章。
另外还有一种题二叉树是存储成数组形式的这时就要利用以下关系根节点从0开始编号对于任意一个节点 i其左孩子编号为 2i1右孩子编号为 2i2代码如下
#
# 对给定的二叉树依次完成前序中序后序遍历并输出遍历结果
# param input int整型一维数组 -1表示Nil节点
# return int整型二维数组
#
# 定义一个二维列表
results [[]for i in range(3)]
class Solution:def binaryTreeScan(self , input ):# write code here# 前序遍历def preOrder(root):if rootlen(input):if input[root]!-1:results[0].append(input[root])preOrder(root*21)preOrder(root*22)# 中序遍历def inOrder(root):if rootlen(input):inOrder(root*21)if input[root]!-1:results[1].append(input[root])inOrder(root*22)# 后序遍历def postOrder(root):if rootlen(input):postOrder(root*21)postOrder(root*22)if input[root]!-1:results[2].append(input[root])preOrder(0)inOrder(0)postOrder(0)return results
