记忆点：
- 前序：VLR
- 中序：LVR
- 后序：LRV
举例：
一颗二叉树如下图所示：
则它的前序、中序、后序遍历流程如下图所示：
1.前序遍历
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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.中序遍历
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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.后序遍历
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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.测试
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
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(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
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: TreeNode): # 后序
def postorder(root: TreeNode): if not root: return postorder(root.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叉树前序遍历
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
""" # 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 |
