（1）前序遍历
传送门：144. 二叉树的前序遍历（简单题）
前序遍历：先访问根节点——>左子树——>右子树。
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.preorder(root, res)
return res
def preorder(self, root, res):
if root:
res.append(root.val)
self.preorder(root.left, res)
self.preorder(root.right, res)
（2）中序遍历
传送门：94. 二叉树的中序遍历（简单）
中序遍历：先访问左子树 ——> 根节点 ——> 右子树。
from typing import List
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.inorder(root, res)
return res
def inorder(self, root, res):
if root:
self.inorder(root.left, res)
res.append(root.val)
self.inorder(root.right, res)
（3）后序遍历
传送门：145. 二叉树的后序遍历（简单）
后序遍历：先访问树的左子树 ——> 右子树 ——> 根节点。
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.postorder(root, res)
return res
def postorder(self, root, res):
if root:
self.postorder(root.left, res)
self.postorder(root.right, res)
res.append(root.val)
（4）层序遍历
传送门：102. 二叉树的层序遍历（中等）
层序遍历：把一棵树从上到下，从左到右依次写出来。
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
from collections import deque
ans = []
queue = deque()
queue.append(root)
while len(queue) > 0: # 只要队不空
cur = []
for _ in range(len(queue)):
node = queue.popleft()
cur.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(cur)
return ans
|