二叉树的dfs 与 bfs (递归遍历)
dfs
深度优先遍历包含前中后
递归思路
递归三要素,终止条件 ,逻辑, 返回
二叉树结构
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
前序 根左右
//前序遍历 跟左右
void traversal(TreeNode root ,List<Integer> res){
if(root != null){
res.add(root.val);
traversal(root.left,res);
traversal(root.right,res);
}else {
return;
}
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
traversal(root,res);
return res;
}
中序 左根右
void traversal(TreeNode root ,List<Integer> res){
if(root != null){
traversal(root.left,res);
res.add(root.val);
traversal(root.right,res);
}else {
return;
}
}
后续 左右根
//后续遍历 左右根
void traversal(TreeNode root ,List<Integer> res){
if(root != null){
traversal(root.left,res);
traversal(root.right,res);
res.add(root.val);
}else {
return;
}
}
bfs
广度优先代表是层序遍历
void dfs(TreeNode root,int level,List<List<Integer>> res){
//终止条件
if(root == null) return ;
//逻辑
if(level>=res.size()){
res.add(new ArrayList<>());
}
res.get(level).add(root.val);
dfs(root.left,level+1,res);
dfs(root.right,level+1,res);
//返回
}