门户网站建设 报告,班级网站建设,手机网站的模板下载,客户管理系统crm记录一下算法题的学习7
二叉树的最大深度
题目#xff1a;给定一个二叉树 root #xff0c;返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 输入#xff1a;root [3,9,20,null,null,15,7]
输出#xff1a;3
示例分析#xff…记录一下算法题的学习7
二叉树的最大深度
题目给定一个二叉树 root 返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 输入root [3,9,20,null,null,15,7]
输出3
示例分析
这里根节点为3叶子节点是什么呢----是指没有子节点的节点记录从根节点到最远叶子节点的最长路径上的节点数那么就是3-20-15或者3-20-7一共是3个节点数
怎么体现呢
深度优先搜索代码展示
class Solution {public int maxDepth(TreeNode root) {//首先输入根节点为空的情况下二叉树就不存在 if(rootnull){return 0;}//判断输入根节点不为空存在二叉树else{int leftDepthmaxDepth(root.left); //得到根节点root左子树的最长路径上的节点数int rightDepthmaxDepth(root.right);//得到根节点root右子树的最长路径上的节点数return Math.max(leftDepth,rightDepth)1;//由题目可知还需加上代表根节点的节点数1}}
}
广度优先搜索代码展示
这里进行回忆记录Queue
Queue是java中实现队列的接口它总共有6个方法我们一般只用其中3个就可以了。Queue的实现类有LinkedList和PriorityQueue。最常用的实现类是LinkedList。 方法 作用区别 add( 压入元素(添加)相同未超出容量从队尾压入元素返回压入的那个元素。 区别在超出容量时add()方法会对抛出异常offer()返回falseoffer()压入元素(添加)remove弹出元素删除相同容量大于0的时候删除并返回队头被删除的那个元素。 区别在容量为0的时候remove()会抛出异常poll()返回falsepoll弹出元素删除element获取对头元素相同容量大于0的时候都返回队头元素。但是不删除。 区别容量为0的时候element()会抛出异常peek()返回null。peek获取对头元素
class Solution {public int maxDepth(TreeNode root) {//首先输入根节点为空的情况下二叉树就不存在 if(rootnull){return 0;}QueueTreeNode queuenew LinkedList();//初始化队列queuequeue.offer(root);//将根节点加入队列中int result0;//初始化结果while(!queue.isEmpty()){ //队列不为空的情况即刚才加入的根节点nullint sizequeue.size();//取出当前队列的长度while(size--0){//取出相同数量的节点数进行遍历TreeNode nodequeue.poll();if(node.left!null){queue.offer(node.left);}if(node.right!null){queue.offer(node.right);}}result; }return result;}
} 二叉树的最小深度
题目给定一个二叉树找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 输入root [3,9,20,null,null,15,7]
输出2输入root [2,null,3,null,4,null,5,null,6]
输出5示例分析
如果我们直接将二叉树的最大深度的代码直接拿来用就会报错因为我们忽略了还有一种情况左孩子和右孩子有一个为空的情况但不确定是哪一个我们返回leftDepthrightDepth1在求二叉树的最小深度中。 深度优先搜索代码展示
class Solution {public int minDepth(TreeNode root) {//首先输入根节点为空的情况下二叉树就不存在 if(rootnull){return 0;}//1.左孩子和右孩子都为空的情况说明到达了叶子节点直接返回1if(root.left null root.right null){return 1;}int leftDepthminDepth(root.left); //得到根节点root左子树的最短路径上的节点数int rightDepthminDepth(root.right);//得到根节点root右子树的最短路径上的节点数//2.左孩子和右孩子有一个为空的情况但不确定是哪一个我们返回leftLengthrightLength1if(root.left null || root.right null){return leftDepthrightDepth1;//3 左孩子和右孩子都不为空的情况那就比较出两者之间更小的值然后再加一得到最小深度}else{return Math.min(leftDepth,rightDepth)1;//由题目可知还需加上代表根节点的节点数1} }
}广度优先搜素代码展示
class Solution {public int minDepth(TreeNode root) {//首先输入根节点为空的情况下二叉树就不存在 if(rootnull){return 0;}QueueTreeNode queue new LinkedList();queue.offer(root);int result1;while (!queue.isEmpty()) {int sizequeue.size();for(int i0;isize;i){TreeNode node queue.poll();if (node.left null node.right null) {return result;}if (node.left ! null) {queue.offer(node.left);}if (node.right ! null) {queue.offer(node.right);}}result;}return result;}
}
注意这里必须这样写 不能直接写成forint i0;iqueue.size();i),因为queue.size()一直在变化加入一个就变化一次无法完成每次循环遍历每层内容,但是可以写成for(int iqueue.size()-1;i0;i--)。
