image.png
前序遍历
先访问根节点，再前序遍历左子树，再前序遍历右子树。
-
递归解法
一般会新增一个 dfs 函数：def dfs(root): if not root: return res.append(root.val) dfs(root.left) dfs(root.right)前序遍历的代码如下：
class Solution(object): def preorderTraversal(self,root:TreeNode): res = [] def dfs(root): nonlocal res if not root: return res.append(root.val) dfs(root.left) dfs(root.right) dfs(root) return res 迭代解法
使用栈来模拟迭代。因为先序遍历是根左右的顺序，栈是先进后出。
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack,res = [],[]
cur = root
while stack or cur:
while cur:
res.append(cur.val)
stack.append(cur)
cur = cur.left
cur = stack.pop()
cur = cur.right
return res
中序遍历
先中序遍历左子树，再访问根节点，再中序遍历右子树
- 递归解法
class Solution(object):
def preorderTraversal(self,root:TreeNode):
res = []
def dfs(root):
nonlocal res
if not root:
return
dfs(root.left)
res.append(root.val)
dfs(root.right)
dfs(root)
return res
- 迭代解法
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack,res = [],[]
curr = root
while stack or curr:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop();
res.append(curr.val);
curr = curr.right;
return res
后序遍历
先后序遍历左子树，再后序遍历右子树，再访问根节点
- 递归解法
class Solution(object):
def preorderTraversal(self,root:TreeNode):
res = []
def dfs(root):
nonlocal res
if not root:
return
dfs(root.left)
dfs(root.right)
res.append(root.val)
dfs(root)
return res
- 迭代解法
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res,stack = [],[]
cur = root
while stack or cur:
while cur:
res.append(cur.val)
stack.append(cur)
cur = cur.right
cur = stack.pop()
#res.append(cur.val)
cur = cur.left
#res.append(cur.val)
return res[::-1]
层序遍历
二叉树的层次遍历的迭代方法与前面不用，因为前面的都采用了深度优先搜索的方式，而层次遍历使用了广度优先搜索，广度优先搜索主要使用队列实现，也就不能使用前面的模板解法了。
image.png
image.png
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return [] # 特殊情况，root为空直接返回
from collections import deque
# 下面就是BFS模板内容，BFS关键在于队列的使用
layer = deque()
layer.append(root) # 压入初始节点
res = [] # 结果集
while layer:
cur_layer = [] # 临时变量，记录当前层的节点
for _ in range(len(layer)): # 遍历某一层的节点
node = layer.popleft() # 将要处理的节点弹出
cur_layer.append(node.val)
if node.left: # 如果当前节点有左右节点，则压入队列，根据题意注意压入顺序，先左后右，
layer.append(node.left)
if node.right:
layer.append(node.right)
res.append(cur_layer) # 某一层的节点都处理完之后，将当前层的结果压入结果集
return res
