二叉树前序、中序、后序遍历-python

怼烎@ 2023-07-25 09:20 71阅读 0赞

一、中序遍历

  1. def inorderTraversal(root):
  2.     if not root:
  3.         return []
  4.     return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)
  6. def inorderTraversal(root):
  7.     stack = []
  8.     sol = []
  9.     curr = root
  10.     while stack or curr:
  11.         if curr:
  12.             stack.append(curr)
  13.             curr = curr.left
  14.         else:
  15.             curr = stack.pop()
  16.             sol.append(curr.val)
  17.             curr = curr.right
  18.     return sol

二、前序遍历

  1. def preorderTraversal(root):
  2.     if not root:
  3.         return []
  4.     return [root.val] + inorderTraversal(root.left) + inorderTraversal(root.right)
  6. def preorderTraversal(root):
  7.     stack = []
  8.     sol = []
  9.     curr = root
  10.     while stack or curr:
  11.         if curr:
  12.             sol.append(curr.val)
  13.             stack.append(curr.right)
  14.             curr = curr.left
  15.         else:
  16.             curr = stack.pop()
  17.     return sol

三、后序遍历

  1. def postorderTraversal(root):
  2.     if not root:
  3.         return []
  4.     return inorderTraversal(root.left) + inorderTraversal(root.right) + [root.val]
  6. def postorderTraversal(root):
  7.     stack = []
  8.     sol = []
  9.     curr = root
  10.     while stack or curr:
  11.         if curr:
  12.             sol.append(curr.val)
  13.             stack.append(curr.left)
  14.             curr = curr.right
  15.         else:
  16.             curr = stack.pop()
  17.     return sol[::-1]

发表评论

表情：
评论列表 （有 0 条评论，71人围观）

还没有评论，来说两句吧...

相关阅读