上海未成年人思想道德建设网站,莘县制作网站,深圳东门属于哪个街道,wordpress主题织梦目录 深度优先算法#xff08;Depth-First Search#xff0c;DFS#xff09;
LeetCode之路——102. 二叉树的层序遍历
分析 深度优先算法#xff08;Depth-First Search#xff0c;DFS#xff09;
DFS是一种用于遍历或搜索树状数据结构的算法#xff0c;其中它首先探…目录 深度优先算法Depth-First SearchDFS
LeetCode之路——102. 二叉树的层序遍历
分析 深度优先算法Depth-First SearchDFS
DFS是一种用于遍历或搜索树状数据结构的算法其中它首先探索树的深度然后回溯并继续探索其他分支。在二叉树中深度优先算法可以通过递归或使用栈来实现。有三种常见的深度优先遍历方式前序遍历、中序遍历和后序遍历每种方式都对节点的访问顺序略有不同。 以下是深度优先遍历的Java代码示例包括前序遍历、中序遍历和后序遍历
class TreeNode {int data;TreeNode left;TreeNode right;
public TreeNode(int data) {this.data data;}
}
// 前序遍历Preorder DFS
void preorderDFS(TreeNode node) {if (node null) return;System.out.print(node.data ); // 先访问根节点preorderDFS(node.left); // 遍历左子树preorderDFS(node.right); // 遍历右子树
}
// 中序遍历Inorder DFS
void inorderDFS(TreeNode node) {if (node null) return;inorderDFS(node.left); // 遍历左子树System.out.print(node.data ); // 访问根节点inorderDFS(node.right); // 遍历右子树
}
// 后序遍历Postorder DFS
void postorderDFS(TreeNode node) {if (node null) return;postorderDFS(node.left); // 遍历左子树postorderDFS(node.right); // 遍历右子树System.out.print(node.data ); // 最后访问根节点
}
LeetCode之路——102. 二叉树的层序遍历
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 示例 1 输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]]
示例 2
输入root [1]
输出[[1]]
示例 3
输入root []
输出[] 提示 树中节点数目在范围 [0, 2000] 内 -1000 Node.val 1000 分析
逐层地从左到右访问所有节点这种情景叫做树的层序遍历。匹配的算法是DFS(Depth-first search)和BFS(Breadth-first search)。
// DFS算法-前序遍历
class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger resList new ArrayListListInteger();dfsPreorder(root, 0, resList);return resList;}/*** 前序遍历的DFS* param node* param deep*/public static void dfsPreorder(TreeNode node, int deep, ListListInteger resList) {if (node null) return;deep;
if (resList.size() deep) {// 用resList的索引标记层数ListInteger list new ArrayList();resList.add(list);}resList.get(deep - 1).add(node.val);
//左侧子节点遍历dfsPreorder(node.left, deep, resList);//右侧子节点遍历dfsPreorder(node.right, deep, resList);}} 时间复杂度O(n) 空间复杂度O(n)
