Python 递归式实现二叉树前序,中序,后序遍历

目录

• 1.前序遍历
• 2.中序遍历
• 3.后序遍历
• 4.测试
• 5.结果
• 6.补充
• 6.1N叉树前序遍历

记忆点：

• 前序：VLR
• 中序：LVR
• 后序：LRV

举例：

一颗二叉树如下图所示：

则它的前序、中序、后序遍历流程如下图所示：

1.前序遍历

class Solution:
  def preorderTraversal(self, root: TreeNode):
 
    def preorder(root: TreeNode):
      if not root:
        return
      res.append(root.val)
      preorder(root.left)      
      preorder(root.right)
     
    res = []
    preorder(root)
    return res

2.中序遍历

class Solution:
  def inorderTraversal(self, root: TreeNode):
  
    def inorder(root: TreeNode):
      if not root:
        return
      inorder(root.left)
      res.append(root.val)
      inorder(root.right)
   
    res = []
    inorder(root)
    return res

3.后序遍历

class Solution:
  def postorderTraversal(self, roo编程客栈t: TreeNode):
  
    def postorder(root: TreeNode):
      if not root:
        return
      postorder(root.left)
      res.append(root.val)
      postorder(root.right)
   
    res = []
    postorder(root)
    return res

4.测试

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

# 用列表递归创建二叉树
def createTree(root,list_n,i)编程客栈:
 if i <len(list_n):
  if list_n[i] == 'null':
    return None
  else:
   root = TreeNode(val = list_n[i])
   root.left = createTree(root.left,list_n,2*i+1)
   root.right = createTree(root.right,list_n,2*i+2)
   return root 
  return root
  
class Solution:
 def preorderTraversal(s编程客栈elf, root: TreeNode): # 前序
 
  def preorder(root: TreeNode):
   if not root:
    return
   res.append(root.val)
   preorder(root.left)      
   preorder(root.right)
   
  res = []
  preorder(root)
  return res

 def inorderTraversal(self, root: TreeNode): # 中序
 
  def inorder(root: TreeNode):
   if not root:
    return
   inorder(root.left)
   res.append(root.val)
   inorder(root.right)
   
  res = []
  inorder(root)
  return res
  
 def postorderTraversal(self, root: Tre编程客栈eNode): # 后序
 
  def postorder(root: TreeNode):
   if not root:
    return
   postorder(roo编程客栈t.left)
   postorder(root.right)
   res.append(root.val)
   
  res = []
  postorder(root)
  return res

if __name__ == "__main__":

 root = TreeNode()
 list_n = [1,2,3,4,5,6,7,8,'null',9,10]
 root = createTree(root,list_n,0)
 s = Solution()
 res_pre = s.preorderTraversal(root)
 res_in = s.inorderTraversal(root)
 res_post = s.postorderTraversal(root)
 print(res_pre)
 print(res_in)
 print(res_post)

5.结果

6.补充

6.1N叉树前序遍历

"""
# Definition for a Node.
class Node:
  def __init__(self, val=None, children=None):
    self.val = val
    self.children = children
"""

class Solution:
  def postorder(self, root: 'Node') -> List[int]:
    def seq(root):
      if not root:
        return
      res.append(root.val)
      for child in root.children:
        seq(child)      
    res = []
    seq(root)
    return res

N叉树后序遍历
"""
# Definition for a Node.
class Node:
  def __init__(self, val=None, children=None):
    self.val = val
    self.children = children
"""

class Solution:
  def postorder(self, root: 'Node') -> List[int]:
    def seq(root):
      if not root:
        return
      for child in root.children:
        seq(child)
      res.append(root.val)
    res = []
    seq(root)
    return res

到此这篇关于python 递归式实现二叉树前序,中序,后序遍历的文章就介绍到这了,更多相关二叉树前序,中序,后序遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！