做网站的算什么行业,网页广告图,网页模板下载后怎么用,下载网址【问题描述】[简单]
输入一棵二叉树的根节点#xff0c;求该树的深度。从根节点到叶节点依次经过的节点#xff08;含根、叶节点#xff09;形成树的一条路径#xff0c;最长路径的长度为树的深度。例如#xff1a;给定二叉树 [3,9,20,null,null,15,7]#xff0c;3/ \9 …【问题描述】[简单]
输入一棵二叉树的根节点求该树的深度。从根节点到叶节点依次经过的节点含根、叶节点形成树的一条路径最长路径的长度为树的深度。例如给定二叉树 [3,9,20,null,null,15,7]3/ \9 20/ \15 7
返回它的最大深度 3 。
【解答思路】
1. 后序遍历DFS 时间复杂度O(N) 空间复杂度O(N)
class Solution {public int maxDepth(TreeNode root) {if(root null) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right)) 1;}
}2. 层序遍历BFS
树的层序遍历 / 广度优先搜索往往利用 队列 实现。 关键点 每遍历一层则计数器 11 直到遍历完成则可得到树的深度。 算法解析 1.特例处理 当 root 为空直接返回 深度 00 。 2.初始化 队列 queue 加入根节点 root 计数器 res 0。 3.循环遍历 当 queue 为空时跳出。 4.统计层数 执行 res 1 代表层数加 1 5.获取当前queue的size遍历队列 遍历 queue 中的各节点 node 并将其左子节点和右子节点加入 tmp 6.返回值 返回 res 即可。
时间复杂度O(N) 空间复杂度O(N) public int maxDepth(TreeNode root) {if (root null) return 0;QueueTreeNode queue new LinkedList();queue.add(root);int res 0;while (!queue.isEmpty()) {res;int n queue.size();for (int i 0; i n; i) {TreeNode node queue.poll();if (node.left ! null) queue.add(node.left);if (node.right ! null) queue.add(node.right);}}return res;}【总结】
1.树的遍历方式总体分为两类深度优先搜索DFS、广度优先搜索BFS
常见的 DFS 先序遍历、中序遍历、后序遍历 常见的 BFS 层序遍历即按层遍历。
2.LinkedList 基本使用
添加 删除 获取 队列 add/offer remove/poll peek 栈 offer/push poll/pop peek 总结
转载链接https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/solution/mian-shi-ti-55-i-er-cha-shu-de-shen-du-xian-xu-bia/
