建网站用的域名多少钱,建设网站是否等于开展网络营销,各大网站网络推广的收费,法库网站建设树的遍历#xff0c;dfs与bfs基础。
题目 注意这种题要看根节点的深度是0还是1。
深度优先遍历dfs#xff0c;通过递归分别计算左子树和右子树的深度#xff0c;然后返回左右子树深度的最大值再加上 1。递归会一直向下遍历树#xff0c;直到达到叶子节点或空节点。在回溯…树的遍历dfs与bfs基础。
题目 注意这种题要看根节点的深度是0还是1。
深度优先遍历dfs通过递归分别计算左子树和右子树的深度然后返回左右子树深度的最大值再加上 1。递归会一直向下遍历树直到达到叶子节点或空节点。在回溯过程中计算每一层的深度并返回最终求得整棵树的最大深度。
时间复杂度O(n)空间复杂度O(n)最坏情况或 O(log n)最佳情况。
/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {public int maxDepth(TreeNode root) {if (root null) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right)) 1;}
}广度优先遍历bfs逐层遍历从树的第一层开始逐渐访问下一层。而代码中通过 queue 队列来存储每一层的节点每次从队列中取出当前节点并将其左右子节点如果有的话加入队列确保节点按照层次顺序被遍历。下一层的节点会在当前层的节点都处理完之后才开始被访问。
时间复杂度是 O(n)空间复杂度是 O(n)。
/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {public static int maxDepth(TreeNode root) {if (root null) return 0; // 如果树为空深度为0QueueTreeNode queue new LinkedList(); // 使用队列queue.add(root); // 将根节点加入队列int depth 0; // 用来记录深度while (!queue.isEmpty()) { // 当队列不为空时继续遍历int size queue.size(); // 当前层节点的数量for (int i 0; i size; i) { // 遍历当前层的每个节点TreeNode node queue.poll(); // 从队列头部移除节点if (node.left ! null) queue.add(node.left); // 如果左子树存在加入队列if (node.right ! null) queue.add(node.right); // 如果右子树存在加入队列}depth; // 当前层处理完后深度加1}return depth; // 返回最大深度}
}
