日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Python?遞歸式實現二叉樹前序,中序,后序遍歷_python

作者：步木木 ? 更新時間： 2022-05-07 編程語言

記憶點：

  • 前序：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, root: 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

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

原文鏈接：https://blog.csdn.net/weixin_44241793/article/details/123280376

欄目分類
最近更新