二叉树的DFS、BFS遍历（包括递归与非递归算法）

一、 DFS遍历

DFS遍历（深度优先搜索）包括中序、先序、后序搜索

1、中序遍历的递归算法如下：

# 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 zhongxu(self, root: TreeNode) -> List[int]: a = [] def dfs(root): if not root: return list() dfs(root.left) a.append(root.val) dfs(root.right) dfs(root) return a

中序遍历的非递归算法如下：

# 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 zhongxu(self, root: TreeNode) -> List[int]: stack = [] result = [] pi = root while stack or pi: if pi: stack.append(pi) pi = pi.left else: pi = stack.pop() result.append(pi.val) pi = pi.right return result

2、先序遍历的递归算法如下

def preorderTraversal(self, root: TreeNode) -> List[int]: a = [] def xianxu(root): if not root: return list() a.append(root.val) xianxu(root.left) xianxu(root.right) xianxu(root) return a

非递归算法：

def xianxu(self, root: TreeNode) -> List[int]: if not root: return list() stack = [root] result = [] while stack: node = stack.pop() result.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result

二、 BFS遍历（广度优先搜索）

非递归算法：

def bfs(self, root: TreeNode) -> List[List[int]]:: if not root: return list() queue = [root] result = [] while queue: cur = [] n = len(queue) for i in range(n): node = queue.pop(0) cur.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(cur) return result