技智网站建设小编,高性能网站建设进行指南,精美ppt模板免费下载百度云,百度搜索竞价104. 二叉树的最大深度
题目链接
题目描述#xff1a; 给定一个二叉树#xff0c;找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例#xff1a; 给定二叉树 [3,9,20,null,null,15,7]#xff0c…104. 二叉树的最大深度
题目链接
题目描述 给定一个二叉树找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例 给定二叉树 [3,9,20,null,null,15,7] 返回它的最大深度 3 。
难点
思路 递归法递归地遍历左右子树返回较大的深度值 迭代法使用层序遍历结果集中的层数就是二叉树最大的深度~
时间复杂度O() 空间复杂度O()
/*** 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;}
}//迭代法——使用层序遍历
class Solution {ListListInteger resList new ArrayList();public int maxDepth(TreeNode root) {if (root null) return 0;DequeTreeNode que new ArrayDeque();que.addLast(root);TreeNode cur;int len;while (!que.isEmpty()) {len que.size();ListInteger itemList new ArrayList();for (int i 0; i len; i) {cur que.pollFirst();itemList.add(cur.val);if (cur.left ! null) que.addLast(cur.left);if (cur.right ! null) que.addLast(cur.right);}resList.add(itemList);}return resList.size();}
}二叉树节点的深度指从根节点到该节点的最长简单路径边的条数。二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数。
因为求深度可以从上到下去查 所以需要前序遍历中左右而高度只能从下到上去查所以只能后序遍历左右中
有的同学一定疑惑为什么104.二叉树的最大深度 (opens new window)中求的是二叉树的最大深度也用的是后序遍历。
那是因为代码的逻辑其实是求的根节点的高度而根节点的高度就是这棵树的最大深度所以才可以使用后序遍历。
class Solution {
public:int result;void getDepth(TreeNode* node, int depth) {result depth result ? depth : result; // 中if (node-left NULL node-right NULL) return ;if (node-left) { // 左getDepth(node-left, depth 1);}if (node-right) { // 右getDepth(node-right, depth 1);}return ;}int maxDepth(TreeNode* root) {result 0;if (root 0) return result;getDepth(root, 1);return result;}
};可以看出使用了前序中左右的遍历顺序这才是真正求深度的逻辑
时长 5min
收获
可以一起做了如下两道题目
104.二叉树的最大深度559.n叉树的最大深度 111. 二叉树的最小深度
题目链接
题目描述 给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7], 返回它的最小深度 2。
难点 递归法的单层递归逻辑
思路 递归法 特别注意当左右子树为空不能直接返回左右子树最小深度。
层序遍历 逐层遍历二叉树如果出现最小深度的叶子那么必定是层序遍历所找到的第一个叶子。
时间复杂度O() 空间复杂度O()
//递归法
class Solution {public int minDepth(TreeNode root) {if (root null) return 0;int leftDepth minDepth(root.left);int rightDepth minDepth(root.right);if (root.left null) {return rightDepth1;}if (root.right null) {return leftDepth1;}return Math.min(leftDepth, rightDepth)1;}
}//层序遍历——优化结果集可不用维护一个List仅维护一个int即可
class Solution {ListListInteger resList new ArrayList();public int minDepth(TreeNode root) {if (root null) return 0;DequeTreeNode que new ArrayDeque();que.addLast(root);while(!que.isEmpty()) {int len que.size();ListInteger itemList new ArrayList();for (int i 0; i len; i) {TreeNode cur que.pollFirst();if (cur.left null cur.right null) {return resList.size()1;}itemList.add(cur.val);if (cur.left ! null) que.addLast(cur.left);if (cur.right ! null) que.addLast(cur.right);}resList.add(itemList);}return resList.size();}
}时长 10min
收获 强化递归练习
加深了层序遍历的理解 222. 完全二叉树的节点个数
题目链接
题目描述 给出一个完全二叉树求出该树的节点个数。
示例 1
输入root [1,2,3,4,5,6]输出6
示例 2
输入root []输出0
示例 3
输入root [1]输出1
提示 树中节点的数目范围是[0, 5 * 10^4] 0 Node.val 5 * 10^4 题目数据保证输入的树是 完全二叉树
难点 层序遍历必能解决换个思路。
刚开始的思路是想拿左下的结点一直拿到倒数第二层这样通过完全二叉树的性质就可以直接计算出前n-1层的个数然后遍历最后一层就行但是问题是仅仅拿到某一层的首个结点并不能遍历这一层的所有节点必须要用队列记录该层的上一层结点。
思路 针对普通二叉树可以使用 递归法、层序遍历
针对完全二叉树 利用完全二叉树的性质 向左拿到leftDepth向右拿到rightDepth 如果leftDepth、rightDepth一致说明是满二叉树直接返回结果 如果不一致那递归地遍历左右子树左右子树可能出现满二叉树
时间复杂度O(log n × log n) 空间复杂度O(log n)
class Solution {/*** 针对完全二叉树的解法** 满二叉树的结点数为2^depth - 1*/public int countNodes(TreeNode root) {if (root null) return 0;TreeNode left root.left;TreeNode right root.right;int leftDepth 0, rightDepth 0; // 这里初始为0是有目的的为了下面求指数方便while (left ! null) { // 求左子树深度left left.left;leftDepth;}while (right ! null) { // 求右子树深度right right.right;rightDepth;}if (leftDepth rightDepth) {return (2 leftDepth) - 1; // 注意(21) 相当于2^2所以leftDepth初始为0}return countNodes(root.left) countNodes(root.right) 1;}
}时长 20min
收获 很有收获再消化消化
